This solution should work for most firewalls, provided the access is not restricted by domain name, and access to regedit is possible.

Click on Start --> Run
Type in "regedit" and then click OK (without the " )

Navigate through the registry editor to:
HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger

Select the "Server" key, Right click, and select "Modify"

Change the value data to:
gateway.messenger.hotmail.com:80

This will connect MSN on port 80, the http port, is working perfectly for me behind a draconian ISP firewall.