Well, I remember on some question where they talk about removing the free-name-changing session when you first register, and how it's a great feature for trolls because they can change their name and they can stay anonymous from the mods.
However, maybe you should give everyone ID codes or somethin'?
So, whenever there is a link on the site, instead of linking to:
It would link to:
(Or something like that, an ID code)
So there will always be an existent link that will link to the same user, no matter what. :D
Of course, there would be a link with the name of the user in the link, in case people who don't know everyone's ID codes can just search by user.
And only considering my username in particular, where it has special characters, you can always type my ID code in the link instead of trying to type the special characters. So everyone would win! ;D