The simple answer is no, you can't use MS Proxy Server v2.0 to do this. ICQ uses TCP/UDP port 4000 and as far as I know ICQ2000 uses the TCP/UDP ports 5190, 5191, 5192 and 5193. MS Proxy Server 2.0 does not allow port filtering unless you use dual NICs and you don't use an upstream proxy. If you do use two NICs and don't have an upstream proxy then you can filter it out by blocking those four TCP and UDP ports.
So what can you do if you are like most of my clients and only have one NIC or have to use an upstream proxy service? You could either upgrade your proxy server to MS ISA and use ISA's superior filtering and Firewall features. ISA is also a more efficient cache. Downside is that ISA requires continual, and I mean continual fine tuning.
Or consider a packet filter like the Packeteer PacketShaper or NetReality WiseWan.
Unless you have VLANs in place and can easily migrate all godlike users onto a "trusted" VLAN and the plebs onto an "untrusted" VLAN, setting up outbound Firewall rules is pretty well useless. If you do have VLANs in place or have physical separation between LANs, then outbound firewall rules become a viable alternative.
For my clients that have a need to control both costs and access, I often put in place a dedicated packet filter and a dedicated cache device. That way we not only are able to block applications either globally or discretely, but improve cache hits (and therfor internet performance and drop costs) as well as prioritise core application by applying Quality of Service rules.
I hope that this helps or at least gives you some options to pursue.