@flyingsaceur where I was running into an issue with PTR records was in that I had the same IP address set as the PTR record for more than one virtual host.
I had always been in the habit of setting a PTR record for everything, but recently I started seeing email get rejected from Gmail if the first result it got when it looked up a PTR didn't match the hostname of the sending server in the mail envelope.
I went through and removed all PTR records for anything that's on a shared IP and isn't functioning as a mail server. Just wondering if there could be some unintended consequences for those hosts not having a PTR.