Ever since I installed Windows Live Messenger a month or so ago I've been unable to add contacts or be added as a contact by others. For a while I was modest enough to assume people had just lied about adding me, but then some more serious requirements for adding people came up and I realised that there was a problem.
Finally, after much searching, I came across this post on the Microsoft newsgroups (link courtesy of Google archiving, yay). Someone had the same problem as me, despite the results of my "research" (read: Googling) this evening seeming to imply that very few people have run into it.
Essentially it came down to an error in the cache that WLM saves in:
– C:\Documents and Settings\[username]\Contacts
– C:\Documents and Settings\[username]\Local Settings\Application Data\Microsoft\Windows Live Contacts
I deleted both folders, and later found out I only really needed to delete the contactcoll.cache files but since the whole of both folders is just cache anyway, I hadn't lost any data.
Make sure Messenger is shut down and then try removing these folders on your PC. Just so you know, it's simply a contact cache, you won't lose anything by doing so.
After doing this, I found I was unable to sign-in to Messenger. But, lo and behold the same newsgroup thread had an answer for that, too: running this registry fix removed some broken policy file and set everything back to normal again.
Your particular problem must've been a problem in the contact cache, which doesn't surprise me as al [sic] the caches in WLM have been quite problematic since it was released.
I signed in and was immediately bombarded with five "add contact" request boxes that must have piled up over the month… one of which was serious and the others which I was just relieved to find had actually been sent after all. So, apologies to those whom I seemed to be ignoring by not accepting their add requests.