Obtenha um melhor provedor de hospedagem. Não há razão alguma que uma instalação que valha a pena pagar não possa criar entradas de DNS inversas apropriadas.
Agora, seja essa a causa de seu e-mail ser sinalizado como spam, bem, você não deu o suficiente para continuar, mas eu consideraria bastante improvável que seu e-mail estivesse sendo amplamente detectado como sendo spam. a menos que o que você está enviando cheire a spam por vários outros motivos, como:
- O rDNS está ativamente errado (como em, ele não faz a viagem corretamente - pontos rDNS para nome, nome não aponta para IP - nesse caso, a ideia de que o provedor de hospedagem não pode mudar o rDNS está claramente errado, porque eles já fizeram isso); ou
- O endereço IP do qual você está enviando tem uma reputação insatisfatória de clientes abusivos anteriores. Neste caso, mais uma vez, o seu provedor de hospedagem não vale a pena ser alimentado, porque eles claramente não têm problemas para hospedar spammers (e, portanto, você está suportando spam, dando-lhes o seu dinheiro).