> A possible implementation would be to allow the user to give a "nickname" to add to usernames he wants to identify uniquely that would be visible only for them. For example since I talk now with you I could add to your username "user with whom I discussed identities and usernames" and this (or a short version of it) would be shown next to your username from now on.

That sounds a bit like SDSI & SPKI's nicknaming functionality. Entities were identified by keyhashes, but you could (and in practice would) give them nicknames or use others' nicknames for them.