Aloga esto es porque no esta pudiento resolver la IP a donde va dirijido el e-mail. Esto puede ser porque el dominio de la dirección de email a donde esta siendo enviado esta mal.
Si utilizas EXIM por ejemplo, estos mensajes los podes ver en la cola con la leyenda **frozen**.
Fijate en el email por ejemplo si pusieron
[email protected] en lugar de hotmail.com ese mail va a responder con un host lookup failed y va a quedar frozen en la cola por el tiempo que tenga determinado la configuración del servidor SMTP.
Para estar mas seguro realiza un ping o un traceroute al dominio del destinatario para corrobar si es válido.
Utiliza
www.dnsstuff.com que trae muy buenas herramientas.
Saludos.