A number of people have had this issue before, and probably still do (I have it too). It seems to be some kind of bug within Messenger, and only fixes itself intermittently. I guess there's not much we can do about it unless the Windows Live team release a new version of Messenger.
/ 
