Microsoft Exchange - Problemon con Exchange server

Buenas;
Tengo un problema que no se identificar con el servidor de Exchange de una de las empresas que llevo. El problema es el siguiente:

Hace 3 días y de buenas a primeras (no pasó nada anormal en la empresa ni en el servidor de correo) el Exchange dejó de enviar correos, mirando el adminitrador de Exchange me salen todos los mensajes en cola intentando enviar el mensaje, pero de el siguiente error:
"El servidor remoto no respondió a un intento de conexión."
He comprobado mediante ping que el smtp de esos correos funciona correctamente, osea si por ejemplo un mensaje va dirigido a gmail, smtp.gmail.com responde correctamente, pero todos los mensajes se quedan parados en la cola y no salen.
Por supuesto he reiniciado el servidor de correo, el router y despues tambien he reiniciado los servicios de Exchange y vuelto a arrancarlos y nada, tambien está activo el servicio smtp en Windows.

De donde puede venir el error?

Si te falta algún dato mas dime algo e intentaré darte mas información.

Un saludo y gracias por adelantado.

Liuvgat

Bueno segun tus datos que envias mensionas que de un momento a otro no funciona tu servdior de correo ...

Los casos que puedan ser es que los servidores de DNS no resuelven los correos que deseas enviar. Otro no esta configurado el el smtp /propiedades /entrega/configurar servidores dns externos o internos.

eso podria decirte por que no detalles como esta destribuido el server y los servicios

Te resolvieron el problema? Como? a mi me pasa lo mismo