In many existing games this is called the "Friends List".
Player-Controlled Categories (Tabs?)
You usually don't just want to keep tabs on friends, you might also want to keep tabs on... all kinds of entities.
Like storyline characters (Anarchy Online has LTCs, Long-Term Characters, which are RPed by volunteers (ARKs), and are (almost) normal characters, so you can add them to your friends list). Not all of those you might want to watch out for are "friends".
Or people you just don't like (gankers, griefers, idiots... you get the idea).
A commenting system is sorely lacking (in all the games I played. Jae). Not just for Contacts, but most importantly for those.
Sharing Contacts across alts. With auto-commenting or markers for which character actually added that contact. So if I see someone on my contacts list online, and want to chat with them, I can introduce this char as "Hi, it's NNN's alt". That would be OOC, of course.
Add an Existing Contact
Adding a contact that already exists in the list would mark this contact as a contact of the current alt too. Good for differentiating contacts that are per-player and per-character.
There could be support for auto-marking contacts you communicate with. You "/tell" (IRC's "/msg" is similar. WoW's /whisper is the same) some character something, and that character gets added (to a separate CL tab).
Ignored characters go into their own tab (by default), so you can see at a glance (okay, depends on the size of the list ;) whom you ignore. And you can take characters off without them being around. (And it would be shared across your chars automatically).
Contacts List and Permadeath
Since a shared contacts list is a per-player thing anyway, a player won't lose his contacts on death of one of his alts. But the contacts made with the deceased alt (only) should be marked in some way. This depends on how much of a focus is put on RP in the game design. Might be so little that no such marking is actually needed. Might be so much that such contacts are "ghosted" in some way, so the player gets hints that none of his characters actually knows that contact.
Automatic Notification When Your Friends Are Playing
There could be a system that allows notification when some of your friends in the contact list are playing (and you are offline), e.g. by email, instant message, SMS, and/or a system tray game accessor.
Perhaps there could be a possibility to configure other such alerts too.