Lad Dir den CCleaner runter, installier den und cleane damit die Registry, soll heißen, das Program sollte eigentlich alle Leichen die MSN, Windows Live und Live Messenger (Plus!) hinterlassen hat löschen, falls Windows erkennt, dass das Programm eigentlich nicht mehr als funktionierend existiert. Funktioniert das nicht machs manuell über Start -> Ausführen -> regedit -> STRG + F -> dort gibst Du dann Live Messenger ein, je nach dem wie das Teil nun heißt (bei mit immernoch Windows Live Messenger) und löscht alles raus was damit zu tun hat. Weitersuchen tust Du mit F3 soweit ich mich erinner. Die aktuelle Version sollte dann gehen, aber eigentlich auch die Alte.
Kleiner Tipp für das nächste Mal: Lösch nie einfach installierte Programme. Wenn es über den Ordner nicht geht, versuchs über die Systemsteuerung, funktionierts damit nicht, nimm ein Programwas von Dritten angeboten wird, CCleaner, TuneUp oder sonstwas.