[Hatifnatt]

Была проблема у меня тоже с mail.ru, IP сервера был вообще в блэклисте и почта тут же возвращалась обратно с заявлением что мол IP blacklisted и отвалите от нас.

Письмо приходило с предложением пройти по адресу
http://win.mail.ru/cgi-bin/support_bl?ip=<IP СЕРВЕРА>
и там заполнить форму после чего IP должен был быть удален из черного списка, заполнял эту фрму раз 5, приходило письмо, что все ок, IP удален, но почта - не ходила как и раньше.
В итоге только с 6-го раза, когда я привел им примеры ~100 других dnsbl где нашего IP не было и заверил что на нашем сервер закрыть relay без авторизации, пришло письмо что тепрь де, IP занесен в белый список. Только после этого почта начала нормально отправляться.