OK, guys, jokes are very funny. Now back to reality. :)
1) Try & block port 1863 outbound on your Proxy. That effectively prevents MSN Messenger to connecting to Microsoft Messenger Service. That in turn prevents communication via MSN Messenger.
2) Note:
Turning off Instant Messaging in Active Directory affects Microsoft Exchange 2000 Messaging services. We in our company have in fact enabled Exchange Instant Messaging for certain group of users who need lightning fast communication without constantly hanging on the phone. This can improve productivity, while MSN Messenger is a private communication tool & some threat to security.
3) If you want to leave MSN Messenger on, just forbid to send files/use voice features, try blockingports 6891-6900 inbound & outbound.
4) "Toss Windows 2000"... Now who's gonna pay for that transition & new Itanium, Mr. Penguin. :)