IM on Company Networks

My CIO wants me to install both MSN and ICQ on our network for each user. I do not think that this is a good idea for security reasons.

Can anyone help me out, I want to know what kind of security holes these programs have. What harm can they do to the network, if any?
Can people hack into a machine through any of the information sent out by IM’s?

Am I being paranoid, or is there a real security threat.

We are running a Win NT 4.0 Server, with msproxy 2.0, and Win2k clients.

Thanks