Не уходит почта с mail.ru на мой домен.

Сначала привязывал его к майл. ру но, поскольку туда не доходила львиная доля писем, привязку удалил и перепривязал к яндексу. Теперь приходят все письма, кроме тех, что отправлены с мейл. ру.
При отправке с мейл. ру возвращается сообщение вида:
1@mydomain.ru
SMTP error from remote mail server after RCPT TO::
host mydomain.ru [37.59.198.13]: 554 5.7.1 :
Relay access denied

либо вида:
1@mydomain.ru
Unrouteable address

Внимание, вопрос! Что мне делать с этой фигней?