Hi John,
Nothing has changed in the Url Re-writer or SiteMap logic in a long time and I'm not seeing any similar issues. If you are seeing incorrect urls in your menu is the site online where I could see it?
If you are just seeing this in your logs and not finding bad links in the menu then it is probably just web bots making up munged urls based on real urls and poking at your site looking for hidden pages or who knows what. I often see 404s in my logs that are clearly from things that manipulate the urls. One very common one I see is that I have some javscript here and there for tracking clicks in google analytics, like for ad clicks I track it as a page view in google analytics using a made up page url that doe snot exist and bots often see those urls in the javascript and try to crawl them but they are not real pages. I also see requests where urls are munged from different pages or sections or are completely made up.
Asad,
Persian characters may not always work for urls, I try to support it but your mileage may vary and behavior of urls with Persian characters can be different in different browsers as discussed here (see the links on this page):
http://www.mojoportal.com/non-ascii-urls.aspx
there are lots of issues with non-ascii characters in urls
Changes may also occur from Windows Updates to IIS or to IE.
Hope it helps,
Joe