Вам нужно гуглить на тему SPF и DKIM. Вероятно почтовики действительно не оценили письма идущие с вашего сервера и заподозрили их в спаме. Тут вариант, либо слать через сторонний сервер smtp (но там могут быть свои ограничения), либо озаботиться вопросом того, что бы ваши письма были "подписаны" по уму. Опять же, посмотрите содержимое заголовков полученного в маил.ру письма, там должны быть заголовки определяющие результаты проверки вашего письма как на "доверительные" заголовки, так и на результаты проверки на спам.
