Se for Windows XP, primeiro deve instalar as duas atualizações abaixo, caso contrário prossiga com os passos de remoção e instalação mais abaixo:
1º - Instala a versão atualizada do "Windows Installer". Baixe do site abaixo:
http://www.microsoft.com/downloads/details.aspx?displaylang=pt-br&FamilyID=5a58b56f-60b6-4412-95b9-54d056d6f9f4#filelist
No final da página, baixe e salve o arquivo:
WindowsXP-KB942288-v3-x86.exe (para Windows XP)
Agora instale esse arquivo e reinicie a máquina.
2º - Baixe e instale o Microsoft .NET Framework versão 2.0 (somente para Windows XP)
http://www.microsoft.com/downloads/details.aspx?displaylang=pt-br&FamilyID=0856eacb-4362-4b0d-8edd-aab15c5e04f5
Clica em "Fazer download", salve em uma pasta depois instale-o.
Remoção do antigo e instalação do novo:
Feche completamente o messenger, clicando com o botão direito no ícone da bandeja (ao lado do relógio), e logo em seguida, em Sair.
1º - Vai no Painel de controle > Adicionar e Remover Programas, e remove o MSN (ou Windows Live Essentials)
2º - Instale o "Windows Installer Cleanup Utility".
http://www.baixaki.com.br/download/windows-installer-cleanup-utility.htm
Abra esse programa, procure e mande remover tudo referente a Windows Live e MSN.
3º - Procure e delete a pasta: "Windows Live" (caso exista).
C:\Arquivos de Programas\Windows Live
C:\Arquivos de Programas\Arquivos comuns\Windows Live
4º - Faça uma limpeza de arquivos temporários e registro com o programa CCleaner,
http://www.baixaki.com.br/download/CCleaner.htm
Obs: Durante a instalação do CCleaner, selecione apenas as duas primeiras opções, desmarque as demais.
5º - Instala o MSN Messenger com o instalador offline abaixo.
Windows Live Messenger versão 2009 build 14.0.8089.726
Você pode baixar o instalador offline direto do site da Microsoft, no link abaixo:
http://wl.dlservice.microsoft.com/download/D/3/A/D3AE83DC-2549-42CA-9B1D-18DAE60318EE/pt-brz/wlsetup-all.exe
Data de lançamento: 19/08/2009
Idioma: Português Brasil
OBS1: Durante a instalação, selecione apenas o "Messenger" (primeira opção), desmarque os outros recursos (Write, Galeria de fotos, etc..)
A não ser que vc precise de algum dos recursos, mas eles não são necessários para o funcionamento do MSN.