Hmm... well, you had not mentioned any sort of a firewall on your network, but such a device is the logical place for enforcing your policy.
ICQ: Clients log into login.icq.com using
5190 TCP. Client to client communication just uses random high (gt 1024) TCP ports. My guess is that if you block 5190 to the login servers, you break ICQ.
(since doing the latter is perhaps more impractical)
Unfortunatly, I wasn't able to find port informtion from AOL as to what IM uses - their homepage for IM has no instructions for firewalling. My suggestion in lieu of this is to just find out what IM is using using your router...
For example, create an ACL for one host that you'll use as a test subject and then do a debug ip packet and then fire up IM on that one host - and
see what you get on your debug output.
You should really only do this if you feel comfortable with the debug functions of IOS - if
used improperly, it could have quite the negative impact on your router.
-Rakesh