Problema: no puedo enviar correos

Buenas noches, por favor necesito ayuda o al menos una orientación.
Desde hoy por la mañana todos los usuarios de mi empresa no pueden enviar correos a ningun dominio, pueden recibir correos pero no enviar.
Usamos el outlook con una cuenta pop3, tenemos un servicio de correos externo. Todos los usuarios estan unidos a un dominio de Active directory en windows Server 2003, ademas salimos por un firewall.

He tratado de configurar una cuenta en otro sitio fuera de mi empresa y no tengo problemas para enviar y recibir, puedo hacer todo eso, lo que me hizo pensar que el problema esta en mi empresa. Tenemos una ip publica fija, que revisando se encuentra en lista negra, de la cual ya he solicitado que me retiren hace como 8 horas, y supuestamente ya estoy fuera de la lista negra, pero aun no puedo enviar correos, he tratado de entrar por webmail y si puedo entrar y ver mis correos pero no puedo enviar mis correos.

Por ultimo coloque mi laptop dentro de la red primero como grupo de trabajo y normal puedo enviar correos, luego lo agregue al dominio, configure una cuenta pop3 y todo normal, puedo enviar y recibir correos, pero en las demas pcs no puedo enviar correos hasta el momento.

A que se puede deber esto??

Gracias.