[exim] Exim suddenly started 'temporarily rejected RCPT', bu…

I run a cluster of four Exim servers, running an older install of Exim 4.

All of a sudden, today, all four have suddenly started responding to every
message received via SMTP with "451 - temporary local problem" and the log
shows "temporarily rejected RCPT <user@domain>". There's no detail on the
end of the line to explain why the address has been rejected.

I know from googling that these issues are usually caused by DNS problems,
however exhaustive tests can find no problem with the DNS on these
machines. Each one runs a local resolver, and the resolv.conf files on
each machine are set to query the local DNS, then another local
general-purpose DNS server in our network, and then the Google public DNS
as a fallback.

The machines can reach all three nameservers, and the "host" command
resolves the domains that are being rejected properly.

Anyone got any idea what might be wrong, or how to debug it?

>From something I saw on a forum I tried running exim -d on some of the
failed addresses. This gets to the 'search_tidyup called' line, where it
hangs and eventually times out with "exim: timed out while reading -
message abandoned"

- J.