Eu faria o seguinte, eles podem não resolver o problema completamente, mas eles melhorarão a capacidade de entrega.
-
Verifique se você tem registros de encaminhamento (A) e reverso (PTR) de seu domínio.
-
Envie um e-mail para sua conta do GMail e verifique os cabeçalhos ("Mostrar original"), geralmente eles incluem muitas informações úteis ("PASS" é bom).
-
Configure o DKIM.
-
Verifique seu IP usando o link . Não deve estar na lista negra.
-
Dê uma olhada no "E-mail Delivery for IT Professionals" do MailChimp, é um guia excelente e detalhado.
Espero que isso ajude.