У меня были подобные проблемы несколько лет назад. К сожалению, не все провайдеры понимают требования к безопасной доставке электронной почты:
- правильная настройка Sender Policy Framework (SPF) в DNS-настройках вашего домена
- корректная подпись DKIM каждого письма (например, с помощью OpenDKIM)
- настройка DMARC в качестве резервного варианта на случай сбоя SPF и DKIM
Эти функции являются обязательными и должны быть реализованы либо на вашем локальном почтовом сервере, либо на ретранслирующем почтовом сервере вашего провайдера. В противном случае исходящая почта будет блокироваться. Например, сервисом gmail.com, но также и многими другими.
В моём случае я использую внешний сервис (duocircle.com) в качестве ретранслятора как для входящей почты (включая защиту от спама), так и для исходящей (SMTP).