rDNS demonstrates some competence on the part of the email server admin, and usually some degree of trust by at least one other admin.
PTR records are controlled by the administrator providing the IP address, in this case the hosting provider. The
MX records demonstrate trust of the administrator in charge of the domain's DNS, in this case you. With few exceptions, legitimate servers pass, but most spambots fail.
If you can't get the correct
A records put in place to pass rDNS validation, use your provider's email relay server to send email. It is unusual for relay servers to have DNS issues. You can still use your own server as your
MX as it does not require rDNS.
While you are updating your DNS, consider adding an SPF policy record if you don't have one. Given this current state of validation software add it as as
TXT record, and if possible as an
SPF record. SPF policies for domains which won't be used for email such as
www.example.com are also recommended.