1) Посмотрите, не попадают ли письма в спам
2) Возможно, требуется подпись dkim для домена
3) Заведите ящики на google, mail, yandex (в сумме это, наверное, 80-90% всех почтовиков), посмотрите, всем не доходят или куда-то конкретно
У меня была ситуация, что не доходило почему-то на mail.ru, или иногда доходило, но падало в Спам.
Написал им, прислал проблемное письмо для анализа в формате eml, они все решили, стало норм.
4) Посмотрите, не попадают ли ваши письма под критерии спама. Например, одна картинка и нет текста.