Проблема решена. Были какие-то непонятки в /etc/hosts
Строка 127.0.0.1 localhost была указана неверно, поэтому отправитель был указан нереальный, а указание заголовка From mail.ru расценивал как подделку отправителя и заворачивал все письма (google и yandex кидал их спам)
Всем спасибо.