[PaleStar]

I could be short and say, "because the story would be a bit shorter if they did". But I'm going to try to answer your questions.

I do not think Sauron would concern himself with where the elves were going if he was trying to rebuild himself and his power. I think that he made note of it, and perhaps thought it weakened the armies that were against him.

The Shire itself has been around for a quite a while; but even if it had been subject to the Witch-king's troublemaking(which it wasn't), the Witch-king would perhaps forget because of the wraithing process?
Besides, and I'm not too sure how accurate I'm being here since I'm shaky on the history and I don't have the book in front of me, I think the Shire was 'founded'(for lack of better word) either at the tail end of the Angmar's 'life'(I mean, by this, the Witch-king rein over it) or escaped it completely. I'm not sure how correct I am by that, though.

Or maybe Sauron was just trying to be difficult. I'm not the most knowledgable person around.

See if that helps.