IM over corporate firewall?

[Gurm]

Well now that you've explained a bit more it's not sooo bad. But I have to admit from my point of view, my job is to make sure that the IT technology always provides the best support for people to do their jobs, and that people don't get the chance to mess up their technology, or their job workflow.

IM is a big no-no in my company, so that shapes my opinion on it. I'm pretty suprised that any large company would allow it since it's very hard to log, and everything really needs logged these days. If the police came to the front door and said that people were transferring child porn to a company's IP addresses through IM, then guess who gets in trouble?

Well it's used extensively intra-company in this particular case, and even extra-company. There are quite a few people whose inability to use SameTime for external IM is having an impact on (I hate the verb "impacting") their productivity.

[Nowhere]

My solution: Jabber/many servers of it works on port 80. When you add transports/gateways (one of features, on the side of server, not client!) to it, you can connect to any major IM network.
(BTW, I would probably take that a bit further: GTalk is a Jabber client, and quite nice to use in cafe/company, so everything above applies to it; only problem is that setting transports on it is slighlty awkward, but it has to be done only once...).
I'd guess that Wikipedia article on Jabber will give you all info/links you'd need if you take that route.
Also here is an English section of a very good local Jabber forum