Проверяли ли вы, внесен ли ваш почтовый домен в черный список? Другая причина может заключаться в том, что получатель ищет запись SPF dns для вашего домена. Вы создали учетную запись SPF?
Почтовые серверы получателя выполняют обратную проверку DNS, чтобы убедиться, что IP-адрес, с которого отправляется почта, авторизован для этого. Почтовые серверы получателя запрашивают DNS для получения SPF и DKIM. Эти записи сообщают почтовому серверу получателя IP-адреса, которым разрешено отправлять электронную почту от имени домена. В идеале создание SPF для вашего домена должно решить вашу проблему.
Если вы использовали свой почтовый сервер без записи SPF, скорее всего, ваш IP-адрес попал в один из нескольких черных списков. Используйте mxlookup (погуглите, пожалуйста) и проверьте, указан ли IP-адрес, и удалите свой IP-адрес. Процедура удаления для каждого из этих списков разная.