I have exactly the same problem in Windows Live 2009. A few second after login the msn do an auto logout. And each time it says " your connection with windows live messenger has been lost , Reconnecting in 30 seconds ". If I keep msn in "Appers Offline" state works well and don't do the auto logout, but in any other status happensb that.
I have solved this before downgrading to Windows Live 2008 that worked perfectly. But now, Microsoft forced the upgrade to 2009 version and we cannot use 2008 anymore. THANKS MICROSOFT! The result is uninstalling Windows Live definitely.