Evitar que usen messenger en una red

Hola,
he intentado varias cosas y no consigo evitar que funcione el messenger.

Os explico mi caso.
Tengo una red con Grupo de Trabajo en una pequeña oficina de unos 25
usuarios conectados mediante switchs.
Hay un servidor exclusivamente para datos.
Hay un router para la conexion ADSL y tiene una dirección mas de la red,
la cual es la puerta de enlace para los PCs.
Todos los PCs tienen Windows XP Profesional SP2, los usuarios tienen
derechos de Administrador y disponen de conexión a Internet.

Quisiera evitar que algunos de los PCs puedan conectarse con el Messenger.
He probado quitando la Excepción de "Messenger" del Firewall de Windows
SP2 y en un principio funcionó pero no iba ni hubo ni conexión a Internet.
Al reiniciar el PC me salió el mensaje del firewall si deseaba permitir el
acceso a internet del programa messenger, le dije que bloqueara pero me
inició sesión y de nuevo todo como antes. Ahora no lo veo en excepciones
del firewall, he probado a deshabilitarlo ejecutando gpedit.msc en
"plantillas administrativas" "Componentes de Windows" "Windows Messenger"
"No permitir que se ejecute Windowws Messenger" - HABILITAR.
Pero nada... sigue funcionando.
También he oído de bloquear en el router el puerto 80 para el PC
determinado
pero no estoy seguro si así también le quito la conexión a internet o solo
messenger.
Ya se que está la solución de desinstalar el Messenger, pero no me
interesa porque pueden volverlo a instalar y no puedo quitar los derechos
de Administrador porque algunos programas no funcionan bien con cuenta de
Usuario.

Gracias por vuestra ayuda.
Salu2