If a player changes his name, it usually shows when you type /seen [player], but not all the time.

I'm assuming this has something to do with a user not being stored in cache.

Maybe get name history from the Mojang API instead?

It's only if the player has played before with the other name on the server.

Yes, I have players that have played on the server for a long time and changed their name. Some of them show, others don't. I assume they aren't being stored in the usermap.