I struggled to get MSN working for behind the firewall I have to face these days. Then I came across Jabber.
Jabber is a open messaging platform which can be used by applications but is great for instant messaging. There's a whole network of servers worldwide that support Jabber. There are several jabber clients that can connect you to the network. The one I use is called Psi. What makes this a nice option is that it allows you to connect to the internet via SSL, so you avoid all those funny ports and protocols that are normally blocked by firewalls [ read more about that here ].
So in theory it's quite easy to get messaging going from behind even the most restrictive firewalls. But then all you're friends are still on MSN? No problem, a lot of Jabber servers, like jabber.org.uk support an MSN “transfer”, which means you just set the transfer up, and all your msn contacts are imported. From then on, everything runs smoothly. There is some minor iretations here and there, for example smileys are displayed as text and not as images, but on the whole, this setup is brilliant !