Bueno realmente esta algo complejo ese problema .

De hecho nunca me a pasado por lo que no tengo una solución concreta para poder ayudarte busque en google haber si alguien había solucionado ese problema y nada..

Pero te dejo la opción:

Vas a desinstalar el windows live con el siguiente programa: Windows Installer CleanUp Utility

Después de haberlo desinstalado con el programa ya mencionado vas a eliminar todas las carpetas, archivos referentes al Messenger incluyendo Addon como msn plus, messenger discovery etc...

Luego Reinicia e instala la versión mas reciente de windows live y cuentas como si funciona o no..

De no funcionar seguimos buscando haber si encontramos la solución.