This isn't really going to help but I do know it is possible to use LDAP for authentication and change both the user name (e.g. from sue.bloggs to sue.jones if Sue gets married) and to just change their last name on the AD end without it making a new account in moodle.
Our settings are almost exactly the same as yours so I think it must be something on the AD end.
AD does incorporate a number of unique identifiers and it seems to me that moodle should use these to link accounts rather than user name or anything like that. I believe it does but I can't see any easy documentation on it. It would certainly make sense to use that.
I would double check how they are being changed and if in changing these details it is changing anything else. Such as any of the unique identifiers. If you are modifying an AD item then they shouldn't change.
If moodle doesn't use GUID or similar then it should. That is unique and shouldn't change. So the first time it would pull over all the accounts then check against the GUID to see if anything has changed. Just because you have chosen username for login then moodle shouldn't bind on that as that can change.
Also as for the argument of never ever changing usernames. Try making someone who has undergone gender realignment keep the username John.Smith you'll quickly find yourself in court in a discrimination case.