The polarization of photons emitted by astrophysical sources might be altered as they travel through a dark matter medium composed of ultra light axion-like particles (ALPs). In particular, the coherent oscillations of the ALP background in the galactic halo induce a periodic change on the polarization of the electromagnetic radiation emitted by local sources such as pulsars. Building up on previous works, we develop a new, more robust, analysis based on the generalised Lomb-Scargle periodogram to search for this periodic signal in the emission of the Crab supernova remnant observed by the QUIJOTE MFI instrument and 20 Galactic pulsars from the Parkes Pulsar Timing Array (PPTA) project. We also carefully take into account the stochastic nature of the axion field, an effect often overlooked in previous works. This refined analysis leads to the strongest limits on the axion-photon coupling for a wide range of dark matter masses spanning 10-23 eV ≲ ma ≲ 10-19 eV. Finally, we survey possible optimal targets and the potential sensitivity to axionic dark-matter in this mass range that could be achieved using pulsar polarimetry in the future.