Alguna vez vi algo similar y no era ningun spy,
Desinstala el messenger, luego ve al panel de control / Agregar y quitar programas / Agregar componentes de windows quita el MSN explorer , reinicia e instala la ultima version de messenger creo que la 7.5, descargalo para instalar mas tarde, asi tendras el instalador en tu pc
Probé lo que dices y no fue pero... encontré una solución parece que era algo del Windows Installer. Lo solucioné ejecutando msiexec/ unreg y msiexec/ regserver. Reinicié y actualizo el Msn al 7.5.
Supuestamente lo soluciono el volver a registrar el MSIExec, que es el Windows Instaler con los comandos de más arriba.
Gracias por los consejos y la ayuda permanente
Saludos