I work behind a very restrictive firewall too, and we (people in my org) realized that the communication in all the clients is happening over http. The clients "tunnel" their protocols over http and hence it works.
If you use gaim, you may want to go to advanced settings and try giving port numbers as 20, 23 and 80 to see if yahoo, gtalk and MSN start working.
Thanks for the interest. But I had tried this in the past and I tried it just now. Does not work. GMail (on GAIM) simpy said 'port x tunneling not allowed', while Yahoo (on GAIM) gave a 'write error' for port 80. Other messages were the same for GTalk.
GAIM would start working out of the box, if the ports are opened. I know this since the ports were opened temporarily and they just worked.
Let me tell this list, that in the period when GAIM was working people (including most Windoze users) became a huge fan of GAIM. GAIM was preferred over and above the GTalk and Yahoo! Messenger clients.
I have not tried it, hence can't comment. But this has been tried in our organization.
With what results?
Cheers, Debarshi