[Exim] Suddenly lots of "host lookup did not complete" error…

Hello list,

All of a sudden today over half, maybe closer to all( I have to experiemtn more) of the emails sent out of
our Exim server send warnings then fail witht the error:

'host lookup did not complete'

Most if not all of the messages in the queue are there because of that and if I do
A host lookup on any of those domains I get all the records back I should.
I don't control any of the erroring domains and both the local name server and our other two nameservers
Return the mx records and the ip address of the mx record like it should.

Any one have any idea what would suddenly start giving that error all the time?

What is Exim trying to do when it gives that error, reverse dns comparison or ???

Thanks

Dan