Здравствуйте, MozgC, Вы писали:

MC> Ну и собственно вопрос — как обычно решаются такие проблемы?
Как минимум нужно чтобы у вашего почтового сервера была PTR запись (соответствующая helo приветствию сервера). Так же желательно использовать SPF и DKIM.
Ну и конечно, если у вас больше всего проблем c mail.ru, спросите у них, как вам от них "защититься".