Reverse lookup - why would recipient's server perform reverse lookup on gateway address?

This is not exactly a Domino configuration question, but I thought a reverse lookup expert here might be able to provide a little insite.

The mail server I am managing is on a network with several other mail servers. All of these servers send mail out through the same gateway. A zone file entry exists that will allow a typical reverse lookup to occur against the mail server’s IP address. When I send mail to my own test external mail addresses, the headers clearly show the sender’s mail server IP and the corresponding reverse lookup entry. All of our mail has been going out fine. However, I recently discovered that we are unable to send mail to one specific small, private domain. The mail log indicates the messages are being rejected because “450 Client host rejected: cannot find your hostname,” and the the IP address listed is not the mail server, but rather our network’s gateway address.

Does anyone know why the recipient’s server might be checking against the gateway rather than the sender’s server IP? Any hints or tips I might be able to pass along to the recipient’s mail admin?

Subject: PTR record

Sometimes issues like this occur if you don’t have a valid PTR record listed in DNS. Check with your DNS provider to see if that’s the case. If so, have them create a PTR record and then see if you’re still having the problem.

Subject: Have seen this but no solution.