[Exim] Unroutable Mail Domain Problem/Possible DNS issue?

Hi All,

I have been suffering from a problem recently with e-mail's to one of the
exim mail servers I administrator rejecting mail with the following
message: -

This message was created automatically by mail delivery software (Exim).

A message that you sent could not be delivered to one or more of its

recipients. This is a permanent error. The following address(es) failed:

<snip> Valid E-Mail Address (this has been checked)

unrouteable mail domain "<snip>"

The problem occurs with multiple different servers so it is not just with
communication with a single server. What I have noticed is that if the
message is sent again it successfully manages to reach the target system. I
believe that the cause of the problem maybe that the DNS is taking to long
to be retrieved by the mail server and that exim is rejecting it as it times
out before the DNS query is answered as it also appears to be a problem only
with systems that are not e-mailed regularly. This could be particularly
true as at the moment the server resides on a low bandwidth line which is
heavily used.

My question is can I extend the time that exim waits for a DNS query to be
returned or get it to retry a few times before bouncing the message back to
the user who the message originated from? Or alternatively if anyone thinks
it may be caused by something other than this I would be glad to hear any
suggestions on how to resolve this issue.

Regards,

Justin Bloom