Sounds like your ISP may have started filtering requests for reverse DNS on non-routable IPs.
What I mean is, if you do a reverse DNS lookup for the IP: 192.168.1.4, your ISP is not going to know the right answer. That IP address is non-routable and is being used all over the world by thousands of companies on their internal network. It can never exist on the open Internet, and thus your ISP can't return an answer for it. IANA resolves these requests to prisoner.iana.org, but recently it seems that due to some concerns over cache poisoning, a lot of DNS operators have stopped answering requests for such reserved IPs.
For a solution, you could either setup your own DNS servers internally to be authoritative just for the reserved IP ranges and forward all other requests to your ISP's DNS server, or you could use a script to add every IP address in your internal network to the /etc/hosts file on each mail server. It would look something like:
Code:
192.168.0.0 reversedns.mydomain.com
192.168.0.1 reversedns.mydomain.com
192.168.0.2 reversedns.mydomain.com
...
192.168.1.0 reversedns.mydomain.com
192.168.1.1 reversedns.mydomain.com
192.168.1.2 reversedns.mydomain.com
...
192.168.254.254 reversedns.mydomain.com
You could also see if it's possible to turn off the reverse DNS features in sendmail so it wouldn't time-out waiting for the answer.