[exim] host lookup did not complete

What's wrong here:

2009-07-13 14:35:32 H=(localhost.localdomain) [127.0.0.1] sender verify
defer for <ndbecker2@???>: host lookup for smtp.hns.com did not
complete (DNS timeout?)
2009-07-13 14:35:32 H=(localhost.localdomain) [127.0.0.1]
F=<ndbecker2@???> temporarily rejected RCPT <ndbecker2@???>:
Could not complete sender verify
2009-07-13 14:35:32 H=(localhost.localdomain) [127.0.0.1]
F=<ndbecker2@???> temporarily rejected RCPT <victor.liau@???>:
Could not complete sender verify
2009-07-13 15:22:32 H=(localhost.localdomain) [127.0.0.1] sender verify
defer for <ndbecker2@???>: host lookup for smtp.hns.com did not
complete (DNS timeout?)

It sounds like this means smtp.hns.com dns lookup failed. But on this same
machine:

host smtp.hns.com
smtp.hns.com is an alias for excore8.hns.com.
excore8.hns.com has address 139.85.52.126
excore8.hns.com has address 139.85.52.156

Any ideas?