[The Squatter of Amon Rûdh]

My understanding was that the Rangers had been watching the borders of the Shire for quite some time before the War of the Ring began in earnest. Also "shadows on the marches" could simply mean that the power of Sauron was waxing again, that an old darkness was returning to Eriador: it doesn't have to mean the Nazgûl.
Maybe the Bucklanders heard dark rumours from Bree, which the author of the poem would have written into his work.