Problema con SMTP en salida

Hola a todos.

Tengo un problema con los mensajes salientes, ya que no consigo enviar
ninguno. En el Event Viewer observo lo siguiente:

"Message delivery to the remote domain 'cualquierdominio.es/com' failed

the following reason: Unable to bind to the destination server in DNS."
Source: SMTPSVC Event ID: 4000

También, en la carpeta \mailroot\queue veo todos los mensajes de salida
encolados (ficheros *.eml) que no logran salir de mi servidor Windows 2000
Server SP4 con el último nivel de parches, según Windows Update.

El puerto 25 está abierto y el firewall revisado, probado, desactivado y
vuelto a activar.

La dirección que he utilizado siempre de salida ha sido 127.0.0.1, y el
servicio me ha funcionado perfectamente hasta hace unos días.

El servicio SMTPSVC también lo he parado y arrancado en múltiples

Los DNS de salida son los habituales de terra (195.235.113.3 y
195.235.96.90), los cuales veo con nslookup perfectamente.

Ningún problema con correo entrante ni con navegación.

¿Se os ocurre algún sitio donde mirar?.

Muchas gracias y un saludo.
Pablo