I am not aware of a difficulty in setting up a PTR record for an IP
address that runs a mail server. We never said it had to equal the
forward DNS or anything else. We just require rDNS and a valid one at that.
Then you must have had a nice provider. When I had an 8-IP block, I
had a hell of a time (and was ultimately unsuccessful in) trying to get my
ISP to either delegate reverse DNS to me or do rDNS for me. I've since
downgraded to 1 (static) IP, and now I at least have rDNS, though according
to SORBS it "looks like a dynamic dialup address" and the ISP won't let me
change it.
Admittedly, my server is just a personal one and may not deserve that
much consideration in the first place, but when implementing policies like
this, keep in mind that not everyone with a mail server has the ability to
manage their own rDNS.
--Andrew Church
achurch(_at_)achurch(_dot_)org
http://achurch.org/