MiXei4

Вероятно сервер думает, что почта находится на этом же сервере и не выпускает её за пределы. У меня была такая проблема с cpanel. Когда удалил почтовый домен из панели — всё встало на свои места. возможно у вас что то подобное.

Попробуйте в поддержку mail.ru.
Только описывайте проблему подробно, прилагайте отчеты об ошибке.
У них правда время ответа до 5 суток кажется и они любят задавать вопросы после этого типа «проблема ещё актуальна?» :)
Но практика показала, что решения технической проблемы типа такой — habrahabr.ru/qa/14500/ от них дождаться можно

Не трогайте A-записи для основного домена (@) и поддомена www.
Остальные нужные записи подскажет гугл при добавлении домена и настройке служб.

Может стоит использовать IMAP? У меня отлично работает на двух машинах.