Sure. Tell them to put in a reverse DNS for their server records and explain to them that it’s for their own good. Checking reverse DNS has been Standard Operating Procedure for some time now; any legit company should have it in place as a matter of course.
Otherwise, since checking DNS is an on/off process as far as I know, unless you can whitelist that particular company in some way, I think you are out of luck. I don’t believe Domino 5.x has the ability to manage white and black lists — you’d need to upgrade your servers to ND6 for that.
If I’m wrong, I’m sure someone else will correct me on this. You can also check the forums, technotes, etc. on IBM’s site for more information.