Problema de envio de mails

Que tal, grupo, mi problema es el siguiente:
Tengo un servidor con NT 4 y Exchange 5.5, y a pesar de que internamente
podemos enviar mail sin problemas, a la hora de enviar al "exterior" el
mensaje se envía, pero a los pocos minutos el servidor devuelve un mail con
lo siguiente:

Your message did not reach some or all of the intended recipients.
Subject: test
Sent: 27/01/2005 07:54 a.m.
The following recipient(s) could not be reached:
mail@mail.com.ar on 27/01/2005 07:55 a.m.
The recipient was unavailable to take delivery of the message

A pesar de que la direccion del destinatario es válida, ya que enviando
desde una cuenta de mail externa funciona perfectamente
Ya revisé desde el Exchange Administrator, en la sección de Conexiones, la
que dice Internet Mail Service, incluso la borré y la cree de nuevo, pero
sigue tirando el mismo mensaje. Tambien chequee el tema de los permisos,
pero no hay restricciones de ningun tipo, y tal como está ahora estaba antes
y se podían enviar sin problemas.

Alguna ayuda???

Gracias

Cesar