Как правильно использовать домен внутренней ретрансляции в MS Exchange чтобы получать письма от Mail.ru?
Обычные редиректы не должны менять содержание письма, а значит не должны портить DKIM-сигнатуру и DMARC в такой ситуации не мешает прохождению письма. Бывают ошибки типа https://support.microsoft.com/en-us/kb/2993556 которые Microsoft устраняет, попробуйте установить последние сервис паки и rollup update'ы.
Возможно именно в вашей конфигурации по каким-то причинам письмо перестраивается, например в настройках формата стоит принудительное изменение формата на RTF/HTML. Я не силен в настройках Exchange, но проверьте чтобы этого не происходило. Попробуйте отправить письмо с любого другого адреса на получателей на обеих серверах, сравните diff'ом результат, чтобы понять, почему бьется DKIM.
И имйте ввиду, что если бьется DKIM-сигнатура письма, значит вы не получаете письма не только от mail.ru, но и от yahoo, aol, linkedin, facebook, Вконтакте, paypal и много кого еще, включая письма от самого гугла (@google.com) - т.к. на всех этих доменах тоже строгий DMARC.
DMARC это технология DKIM + SPF как минимум.
Т.е. у вас проблема с SPF, а не с DKIM, т.к. ваш сервис не входит в диапазоны 
"v=spf1 ip4:94.100.176.0/20 ip4:217.69.128.0/20 ip4:128.140.168.0/21 ip4:188.93.58.0/24 ip4:195.211.128.0/22 ip4:188.93.59.0/24 ip4:128.140.170.0/24 ip4:178.22.92.0/23 ip4:185.5.136.0/22 ip4:5.61.237.0/26 ip4:5.61.237.128/25 ip4:5.61.236.0/24 ~all"
гугл режектит почту, хоть и у мейл.ру не строгое (~all - т.е. решение принять должна принимающая сторона) соответствие, гугл окончательно решает что есть спам, а что не спам.
И наверное тут ничего не сделать, дальше с такими схемами будет только хуже, ибо спамеры уже всех достали.