I've had this same fight with multiple vendors and organizations over the years. Like many others, rDNS should be implement properly. It's just the way to keep a clean house. However, the RFC doesn't require rDNS validation checking, and do to so break mail delivery for many, many legitimate services. Spammers will (actually, have--this idea is old) found new avenues of attack. Reputation scoring, token analysis, and other statistical measures are a far better set of solutions to work with. You can go on the cheap with some sendmail RBL and dspam type solutions all the way up to what I consider best in class right now--Ironport.
A Microsoft shop would probably like FOPE--it integrates well and does a damn nice job of proper spam filtering too. The larger MS shops with EA agreements can roll than into the package for decent pricing.