There is already a thread about the related problem
here.
It appears that Microsoft have a problem with their database, but don't know about it. The only alternative at this point is to either contact Microsoft or create a new account. I have done quite a bit of testing and it has only happened to some accounts. You can test this by creating a new account and all will be fine. Also, you can try logging into messenger on another computer with the troublesome account, and you will get the same error messages.
