[exim] "Unrouteable address" errors

Yesterday I was trying to send an email through our exim 4.50 server.

I kept getting it returned to me with an "Unrouteable address" error.

Checking the logfile I see this:

2007-09-05 15:28:12 1ISvrX-0000d0-Mx ** xxxx@???: Unrouteable address


Could this be caused by some transient DNS problem? There doesn't seem
to be any other information in the logfile that I can use to trace the
cause of the error. This morning I tried the address using 'exim4 -bt
-v' and it seemed to resolve correctly.

The only other odd thing about the address I was sending to was that the
user's full name included non-ASCII characters. The To: line in the
email (sent from Mozilla Thunderbird) was something like:

=?ISO-8859-15?Q?Firstname_L=E4stname?= <xxxx@???>


Could that cause such a problem? As far as I can tell exim didn't even
try to connect to the MX for the domain.

In the end I had to send the mail out via an off-site server, which
worked fine.

Thanks,
Kevin