Reinstalando o Live Messenger - Erro 8007007E

Bom, esse problema eu resolvi remotamente então não tenho muitos detalhes...
De alguma forma o Msn deu problema, e foi desinstalado de alguma forma...
O problema é que ao tentar reinstalar ele, o instalador diz que ele já está instalado, logo, você fica com cara de bobo, porque ele não aparece na lista de remover programas, mas não quer ser instalado...
A solução foi usar a solução proposta aqui:

1. Baixe e instale o Windows Installer Clean Up, instalar como Administrador na opção Executar Como...
2. Executar o Windows Installer Clean Up e, em seguida, procure na lista de entradas:

• (All Users) Windows Live Messenger [14.0.8064.0206]
• (All Users) Windows Live Call [14.0.8064.0206]
• (All Users) Windows Live Communication Platforms [14.0.8064.0206]

clique em "Remover"
E reinstalar o Messenger...
Resolveu, mas continuou o problema que deu causa ao problema (Msn disponível, mas fica offline para os outros).