Cara... não sei se isso te ajuda... mas tenta baixar este messenger for linux...

http://prdownloads.sourceforge.net/a...sn-0_94.tar.gz

Ou mesmo utilizar o http://webmessenger.msn.com

Testa aí... qto ao seu problema... vc ja tentou ver o que os log estáo gerando qdo as máquinas que não funfam o messenger tentam utilizá-los...

oberva aí... pode ser firewall...

T+