У вас с обратной DNS зоной все в порядке? Часто такое бывает, что почтовые системы типа gmail и mail.ru выполняют проверку "grey listing" и помечают их как "спам".
Для начала советую обратиться в поддержку? У них должна быть чёткая инструкция, почему письма отбрасываются.
От mail.ru вы получаете отлуп? (письмо о невозможности доставить сообщение). Если да - покажите его.
И еще. Здесь есть пара-тройка вопросов-ответов о почте по ссылке ниже. Не уверен что сильно поможет, но можно начать с этого:
https://help.mail.ru/mail-help
