Tive problemas semelhantes anos atrás. Infelizmente, nem todos os provedores entendem os requisitos para entrega segura de e-mail:
- Configuração adequada do Sender Policy Framework (SPF) nas configurações de DNS do seu domínio
- Assinatura DKIM adequada de cada e-mail (por exemplo, com OpenDKIM)
- Configuração do DMARC como um backup caso SPF e DKIM falhem
Essas funções são obrigatórias e devem ser implementadas em seu servidor de e-mail local ou no servidor de e-mail de retransmissão do seu provedor. Caso contrário, seus e-mails de saída serão bloqueados. Por exemplo, pelo gmail.com - mas também pela maioria dos outros.
No meu caso, uso um serviço externo (duocircle.com) como retransmissor, tanto para e-mail de entrada (incluindo proteção contra spam) quanto para e-mail de saída (smtp).