Hola
Bueno, un programa de mensajería muy bueno, y en mi opinión mmucho mejor que el de Microsoft, es el trillian:
http://www.ceruleanstudios.com/
Hay mucha gente que no le gusta, basicamente porque no se ve tan bonito como el MSN, pero te diré que este es más rápido, gasta menos memoria y permite conversar en todos o casi todos los sistemas de mensajería que hay (msn,yahoo, icq, irc y AOL).
Pero hablando de tu problema, si tienes bloqueado el puerto a causa del firewall, ninguno te servirá puesto que todos los programas usan las mismas salidas.
Ahora bien, siempre te queda el recurso de utilizar los webchats, no hablarás con tus amigos, pero puedes conversar con otras personas. O tal vez le puedes decir a tus amigos que usen los chats tambien.
Suerte
Felicidad