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?
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):
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,