I did just as you said. I uninstalled both Windows Live Messenger and Messenger Plus, restarted my computer and same problem, when I click Start messenger after the WLM installation is finished, nothing happens (WLM doesnt open) but I see "msnmsgr.exe" in processes.
