Debería tener un desinstalador en Agregar/Quitar programas, hace ya tiempo alguien dio esa solución como acertada
Si no, ¿has probado a quitar completamente el MSN Plus? Y si nada va, intenta pasar un soft antiespías, como Spybot o Ad-Aware, a ver si lo detectan y eliminan.
Suerte