Problema con Exchange 5.5

¿Qué tal?
Desde ayer mi servidor de Exchange 5.5 no me deja enviar correo. Miro en Connections/Internet Mail Service/Queues y se me quedan todos en cola, cuando le doy a detalles a uno de los mail me dice "network error during host resolution". Para recibir no tengo ningún problema solo para enviar, también tengo Internet por lo que hay línea y, últimamente, no se ha tocado absolutamente nada de configuraciones de red, me ha sucedido por las buenas. Mi proveedor insiste en que es mi Exchange el que está dando el problema pero yo lo veo perfecto. En visor de sucesos no me pone nada. Tengo que decir que desde mi servidor nt, en donde tengo instalado el Exchange, no tengo Internet, sí desde los clientes, y no sé porque aquí no tengo de repente, creo que todo está relacionado. También si hago un ping desde el DOS a alguna dirección de web no me responde pero si pongo la ip de esa dirección sí. La verdad es que es una paroia; he parado los servicios e incluso he reiniciado varias veces pero todo sigue igual, como si no tuviera línea con el exterior, cosa que no es así. No sé si podrías echarme una mano.
Muchas gracias y un saludo.