Isn’t this just a result of restoring to an out of date backup?
That aside,
Simple possible change return methods:
a) change gets returned to the address it came from. b) change gets returned to a newly generated bitcoin address.
Most people wont care and will expect the a) behavior, so make this the default. Those who care about the privacy of their transactions can enable b) through some option setting in the client.