Narya and the Shire

[Fordim Hedgethistle]

I don't think we really need anything other than distance and the presence of an ongoing war to explain why it took Sauron a while to find the Shire. Mordor and Hobbiton are about as far apart as Oxford and Zagreb, and with the information he had Sauron only knew that the Shire was somewhere west of the Misty Mountains, which meant he had to scour a chunk of landmass the equivalent of western Europe with extremely limited resources... Sure he had armies at home but he can't rely on them (orcs marching around the West asking for the Shire is going to tip the other guys off...and not be terribly effective).

So he has some spies and the Nazgul and with them alone he has to find a place that even his closest neighbours (who are his enemies and unlikely to tell him) barely believe in!

Imagine being told the name of a single county (or canton, or province, or whatever) somewhere between the Atlantic Ocean, the Arctic Circle, the Mediterranean and Poland and now you have to find it with a handful of spies on horseback (if you're lucky) who have to ride all the way back to you at the Black Sea to report on their progress. I'm surprised he found it at all!