Entre em contato com o hostmaster em seu provedor de hospedagem. Eles devem ser capazes de atualizar o registro PTR para o endereço IP alocado para o seu servidor.
A maioria dos provedores com quem trabalhei ou ouvi falar ajudarão com isso.
Alguns podem ser tão imprudentes a ponto de pedir uma taxa, dependendo do seu nível de serviço existente.
Em alguns casos, eles podem se recusar a alterar o valor do PTR para o FQDN do seu servidor de e-mail, porque eles mesmos o usam para rastreamento de ativos (você veria um valor muito sem sentido como host123.dedicated.dc01.dota.customers.hostingprovider.tld
ou mais)
Se este for o caso, basta alterar seus servidores de e-mail HELO FQDN para o que o PTR resolver.
Eu acredito que você pode controlar isso usando a variável smtpd_banner
em sua configuração de postfix.
Basta alterar $myhostname
(ou o que estiver lá) para host123.dedicated.dc01.dota.customers.hostingprovider.tld
e as verificações de DNS reverso não irão mais falhar