Have you tried running ICQ from behind a firewall? Most games will require the firewall to have specific ports opened to allow this. IF the only connection to the internet is a Web Proxy ICQ, IRC, and just about every game will fail to connect.
Who installed / manages the proxy on the network?