The other day a customer contacted us to say that he was trying to send email from several accounts on one of our servers to an account on another server and it was bouncing back with the following error:

foo@remoteserver.com
Delay reason: SMTP error from remote mail server after RCPT TO::
host remoteserver.com [xxx.xxx.xxx.xxx]: 451 Could not complete sender verify callout

Now I know that our server is fully RFC complient, and the remote server should have no problems performing a sender-verify lookup on any of the ending email addresses. After a bit of poking around and fiddling with exim, I discovered that one of the spam blacklists we used had been taken offline (ordb.org) and when the remote server tried to do a sender verify lookup against our server, the sender-verify connection was timing out before our server finished checking if the remote server was in any blocklists due to the lookup to ordb.org timing out.

A handy little tip for anyone having unexplained sender-verify problems from an otherwise fine exim setup.