Para começar, você precisa de um endereço estático com um registro PTR apontando para o seu registro. Caso contrário, você parece um spammer.
Adicione um registro SPF ao seu servidor de e-mail, permitindo que ele envie um e-mail. Algo como v=spf1 a -all seria apropriado. Eu recomendo servidores de email FQDN (nome de domínio totalmente qualificado) não deve ser o mesmo que o seu nome de domínio. Algo como mail.example.com ou smtp.example.com para o domínio example.com é apropriado. O domínio deve ter um registro SPF como v=spf1 mx ?all , embora eu prefira v=spf1 mx -all quando as coisas estão funcionando.
Considere adicionar uma assinatura DKIM a todos os emails de saída.
Eu fiz uma postagem sobre Como configurar um servidor de e-mail há um tempo atrás. Você pode querer analisá-lo e a minha Política de e-mail .