I suggest you try a truly fresh install of WLM (there's more to it then an uninstall/reinstall though add/remove programs) if uninstalling and reinstalling (with a freshly downloaded WLM installer) after deleting MSN Messenger folder in program files folder doesn't work.
Follow instructions given in:
Completely remove (MSN/Windows Live) Messenger