There is also icq2go.. wich runs in your browser. Indeed, they might be a security issue. Anyway, there are some ways you can stop your nice employees that think they will get away with it.. proxies, and stuff. You may also not allow them to run stuff from their home directories (I don't know how to do it in windows, but in linux, a noexec on /home partition would be enough).
I think the worst problem here would be distraction. Nevertheless, virus dissemination is an issue, and you should be aware of it. But who allowed them to use IM? Tell them off. . Serious. If your politcs doesn't include allowing people to use im, so, they shouldn't be using. You could think about some explanation on this subject, before starting punishment.
Let's now think on what would be the positive points of allowing the use of im instead of prohibiting.. like some have already said, it is an effective and inexpensive way of communication. It's much cheaper to send a PDF than a fax from Brazil to Japan, for instance.