Você deve configurar o Quadro de políticas do remetente e DomainKeys Identified Mail . Ambos são feitos usando DNS e são relativamente simples, desde que você tenha um sistema de e-mail decente. Implementei ambos no Google Apps e no Fastmail sem problemas.
Verifique se seu servidor / domínio não está em listas negras de e-mail - uma ótima ferramenta é MXToolbox . Se eles forem, você terá que seguir os procedimentos da lista negra para tirá-los da lista.
Você também deve configurar o DMARC . Do site deles
DMARC, which stands for “Domain-based Message Authentication, Reporting & Conformance”, is an email authentication protocol. It builds on the widely deployed SPF and DKIM protocols, adding a reporting function that allows senders and receivers to improve and monitor protection of the domain from fraudulent email.
Se você editar sua pergunta para incluir seu nome de domínio, poderá receber conselhos mais específicos para sua situação.