I agree with Ace on using ISA or another firewall/filtering
system.
ISA is the best for such things IF you wish to selectively
allow some users to access such services as it can be
used to restrict base on users and groups which few if
any other program can do.
Regular firewalls/filters are fine if you just wish to stop
everyone -- or are willing to filter by IP address which is
not the same as by the actual user accounts and group
membership.
DNS is fine for preventing the resolution, but recognize
it will NOT actually prevent the connection, just make it
harder to establish (and sometimes practically impossible.)
I actually use the DNS filtering system for some things,
mostly for avoiding visiting unwelcome sites -- for instance
it is fairly easy to knock down a vast majority of rotation
and other ads without affecting the sites you visit in any
material way.
Group Policy can help with some of this, but it's not the
best tool for GENERAL denial of IM, since it is largely
based on Microsoft software* and you would have to work
much harder to knock down AOL and all of the other
possible client-server and peer IM systems.
* Recognizing however, that a GPO can contain an IPSec
policy and with Win2003 software restrictions which offer
both the filtering and another way to attack such problems.
You may end up with a combined solution but I would not
approach the basic problem with DNS nor probably with
the built-in entries of Group Policy either.