начать надо с лог-файлов на сервере а так же прописать обратный адрес и проверять его.
Если письма не доходят, есть 3 варианта:
1) фильтруются в конечной точке (например, спамфильтром или антивирусом)
2) заворачиваются по пути
3) попросту не отправляются.
Что поможет выяснить причину:
1) анализируйте, какие письма не доходят и на какие домены (на самом деле довольно тухлый вариант)
2) анализируйте письма-ответы. Зачастую непрошедшее письмо возвращается обратно с описанием причины блокировки
3) причина "неотправки" должна быть у вас в логах.
Начните с того, что найдите логи отправления всех "недошедших" писем.
