I was in the same situation as you, the new WLM is utter garbage! My messages wouldn't get delivered, it'd sign me out constantly, the facebook integration is a nightmare and although I would be signed in almost 24/7, my contacts couldn't see me or send me offline messages.
I did a thorough uninstall using revo uninstaller (better than add/remove programs) and downloaded the last version that worked for me from here:
http://www.oldapps.com/msn_messenger.php
Version 14 from May 2010 works just fine for me now although it changes my status without me telling it to do so.