As for your actual problem. That is most likely indeed something todo with the servers. Not much you can do about it.
Though you could try this (follow instructions exactly):
CookieRevised's reply to Contacts problem
If that doesn't work you could try to do a complete and clean re-install by following these instructions to the letter:
CookieRevised's reply to Windows Live Messenger BIG PROBLEM!
Try those things, even if you already did them...
After that there is only one thing you could do and that is changing the server you connect to. This could be done with the program you'll find in this post:
Sunshine's reply to AHH I CANT GO ON MSN!
Also, and in any case and no matter what, I would suggest to contact Microsoft about it too so they can fix the problem:
http://support.live.com/eform.aspx?productKey=wlmessenger
/ 
