Настроил exim4.
Письма на mail.ru как бы отправляются, но не доходят.
На сервере telnet mxs.mail.ru 25:
<< EHLO domain.ru
<< MAIL FROM: from_mail@domain.ru
<< RCPT TO: to_mail@inbox.ru
<< DATA
<< Subject: eximt
<<
<< eximtest
<<
<< .
<< QUIT
Письмо нормально приходит.
Если вместо mxs.mail.ru - ставить localhost, то уже нет, только на гугл.