Amigo, você tem muitas opções.
A mais parecida com o MSN é o aMSN. pelo menos que eu conheça, nunca usei esses Mercury, SIm, etc...
O GAIM é muito bom, mas estão muito lentos para desenvolver upgrades, ele funciona com um monte de protocolo (ICQ, Yahoo, etc...)
Atualmente, como estou usando o KDE, utilizo o Kopete, que me surpreendeu. Ele está muito bom mesmo. Utilizo ele porque uso ICQ e Yahoo também, não gosto do MSN. Gostei mais dele do que o GAIM, que sempre usei. O Kopete já vem instalado no KDE.
Abraços....