Software that uses the user's public key as the user's identifier (or potentially something that uses namecoin) do not have this issue - consider tox and ricochet for example.
This isn't really a solution, though. It's just moving the problem somewhere else. The problem then becomes things such as linking existing Third Party Identifiers like email, phone numbers etc. to the users key (which most regular users want to be able to do). The idea of a user per key in general also becomes problematic with multi-device usage or a device compromise. You will not be able to revoke access to any device without throwing away your whole identity.
