А hostname, указанный в настройках почтовика и от имени которого отправляется почта, корректный и существующий? У этого получателя (думаю, не только у него) стоят проверки, которое ваше письмо не проходит.
Протестируйтесь на
www.mail-tester.com и появится ясность, где трабл и что надо подкрутить.