O Windows Messenger - o que vem no Windows XP - não pode ser removido pelos meios, digamos, comuns (Adicionar/remover programas e Adicionar/remover componentes do Windows). Quando isso é feito, é removido apenas o atalho dele no menu iniciar.

Mais existe uma forma bem simples de removê-lo: basta entrar em Iniciar (Start) > Executar (Run), digitar o comando “RunDll32 advpack.dll,LaunchINFSection %windir%\INF\msmsgs.inf,BLC.Removeâ€�  sem as aspas ("") e pressionar no botão OK. Depois de meter, em alguns computadores, pelo menos no meu deu, aparece a barra de eliminar e nela devem ver a apagar os ficheiros do messenger.

E Pronto já não tem o messenger antigo e podem meter o novo (O Windows Live Messenger).