Hi,
thanks for this report, but without more details, it is difficult to say it is bug and how or when it can be fixed.
Plese, try to provide more information on this.
Examples of URLs, how they have changed, when, etc.
Basically, I think that change of valid Itemids may cause this. (this can occur e.g. when you redefine your menu - then purging of the related URLs may be needed). However, I do not see a reason and way how JoomSEF would be changing already generated URLs just with no reason. It is piece of code, not AI. :-)