[Exim] failed to find host name from IP address

We are running exim 3.22 on some Linux boxes

In the last few days, we are having reports that we are bouncing
some mail with 550 errors, from sites we have previously accepted.
The rejectlog has lots of entries of the form

2002-05-03 11:06:22 recipients from [64.156.187.126] refused
(failed to find host name from IP address)

We thought at first this might be a consequence of having helo_verify
set, but the behaviour continues even with it unset.

I've looked in the documentation, but can't see what might be going
on. Can anyone suggest what is happening, please?

--------
Alan Stanier
Essex University Information Systems Services
Systems Group