Yet, if they (your contacts) don't experience any signing out/in problems, then most likely your problem is a problem on the msn servers... These days the MSN servers have had some trouble and some people reported "strange" things happening like contactlists that aren't complete and so on....
If that is the case then there is nothing much you can do. You could try to change the server you connect to, but that's a very long shot. But anyways, for changing the server you must alter the following registry value:
HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger\Server. The best and safest way of doing this is to use "
MSN Servers" a program from Millenium_Edition, you can find it here:
http://kaonet.net/page.php?id=80
Or it's original source:
http://www.freewebs.com/millenium_edition/msnservers.zip
Close MSN Messenger completely (!!!) and start that program, then select a different server (with the least connection and response time)...
/ 
