I am thinking something similar to XMPP/Jabber protocol, if we have all OpenID contacts universally stored on our OpenID servers, like on ClaimID, or MyOpenID, we can connect to all of our contacts very easily on Jyte, Pibb, or other OpenID consumer sites.
Discussion (2)
Could just use FOAF.
Yes, servers can use FOAF and/or XFN microformat, to store contacts information, or otherwise can store this information privately, it depends upon the user's choice.