Display users' name histories/changes on their public profiles, preferably in the Mini Statistics.
Whether or not this can be an optional feature is up for discussion, but if I had to decide, I'd let people choose (via UserCP) to put such "sensitive" information out in the open, just so there's no ranting about invasion of privacy and whatnot.

I'm aware that namechange logs can be dug up in ACP, but it's useful for the regular user to be able to see others' past usernames (no real reason for users not to, anyway).
I recall seeing a suggestion similar to this one in the past, but I wasn't able to find the thread.