Personally, I don't care much about the rename feature.
I will probably never rename myself and I do get annoyed sometimes when I don't know who I'm playing with or when searching for replays that I now can't find because someone renamed themselves again.
Still though, at least from a player perspective, people renaming themselves to SNFPoopieButtholeWheelieNoob seems like harmless fun that quite a few people have fun with and seemingly feel strongly about keeping.
I think the best solution would be some version of what Archsimkat, BlackYps, Tagada and Brutus already laid out: Distinguish display name from account name/id and use the latter for when you really need to identify someone.
I would be much more hesitant to see this solution as viable, because it's yet more work for the devs, but considering @brutus5000 said in Username rules updates:
This would solve a lot of technical problems in the long run.
it might be useful to do anyway.
If all of this is truly a big problem I think the technical solution is the one to go with.