What filter do you have in place?
I’m lazy when it comes to it. I prefer to employ a third party to do it for me. Mail is passed down to me from an SMTP host that has EMF (www.emailsystems.com) installed on it. They also do a managed service.
This seems to be very effective for my situation, since around half the mailboxes on the server belong to minors and they need to have a tight reign kept on them.
They do a trial (http://www.emailsystems.com/business/trial.php) so i’d give that a go before looking at rejecting RDNS failures.
I’m still willing to see what I can come up with if you would like me to, as the problem interests me. I just think that given what you have said that there may be a better method of solving your problem(s)