We have had a few problems with this seemingly "unfirewallable" traffic. We have detected people using ICQ over port 80, and even remote control software over port 80 and it is all a pain in the arse to lock down.

As Tedob1 suggested, monitor your logs (a network IDS may be very useful) and drop this unauthorised traffic at your Firewall or router.

Or you could send out a broadcast message informing your users that doing this is against our standard/policy, and place a filter on your proxy server picking out key words like "icq" etc.. and disciplining the users accordingly.