Яков Светский

Здравствуйте!
Переводя на человеческий язык Ваши настройки:
В SPF-записи указано, что отправка писем Вашего домена может идти только с серверов Майл ру. Если Вы хотите указать возможность отправки с сайта, Вы должны прописывать либо "v=spf1 a include:_spf.mail.ru ~all" либо явно указывая IP - "v=spf1 ip4:100.100.100.100 include:_spf.mail.ru ~all" разумеется вместо сотен подставив свой адрес.
DKIM для сайта тоже не прописан, тот что указан работает только при отправке с серверов Майл ру.
И при этом Вы в DMARC прописываете политику reject, что означает для почтовых серверов, принимающих Ваши письма, отклонять все письма, не прошедшие проверку по DKIM и SPF. При таких настройках ни одно письмо, отправленное с сайта, не попадет даже в папку спам, не говоря уже о папке входящие. И это сильно скажется на репутации Вашего домена, потом тот же гугл даже после хороших настроек будет помещать Ваши письма в спам, комментируя "Ранее похожие письма определялись как спам"
Советую почитать вот эту статью https://7fk.ru/nastroyka-smtp/
Что касается DMARC то желательно прописать на первое время политику none и заодно ruf вместе с fo=1 чтобы видеть все ошибки при проверках.
Что то типа "v=DMARC1; p=none; sp=none; rua=mailto:abuse@domain.com; ruf=mailto:abuse@domain.com; fo=1" подставив вместо abuse@domain.com свою почту

Если идет смена ns-записей, то все почтовые настройки у Вас слетают. Почта настраивается фактически заново, то есть:
1. на хостинге рег ру удаляются их mx-записи, скорее всего они пропишутся автоматически и добавляется mx-запись яндекса
2. SPF-запись скорее всего тоже добавится по умолчанию, ее нужно будет редактировать
3. прописываете DKIM из Яндекс Коннект и если делаете рассылки DMARC

Два решения сходу
1. Переключиться на IMAP
2. Перекинуть эти 80 тысяч в другой ящик или другую папку
Хотя может кто то подскажет правильное решение

Решение с Exchange добавит промежуточных звеньев в Вашей почте, плюс дорогое.
У яндекса последнее время есть недоработки, тоже не самый лучший вариант. Могу предложить два варианта других (G Suite тоже не рассматриваю по причине стоимости).
Во первых Майл Ру для бизнеса, легко переносится с яндекса со всем содержимым, тоже родные приложения, жалоб на нее у пользователей гораздо меньше. Также беплатная и без ограничений по размеру ящиков. Плюс гораздо более оперативная поддержка, среднее время ответа меньше суток. Яндекс мне как то осенью отвечал больше месяца!!! Сразу уточню, при переносе организацию в яндекс коннекте лучше удалить, а то яндекс так и продолжит отправку писем с других ящиков яндекса себе, не глядя на MX.
Второй вариант платный, и более экзотический. Швейцарская Migadu. Без своих приложений, придется использовать сторонние, достаточно простой веб интерфейс. Но четко работающая. На всех платных тарифах неограниченное количество почтовых ящиков, неограниченное количество доменов, нет ограничений по объему. Цены зависят от количества отправляемых писем в день со всех ящиков. До 100 исходящих в день - 5 долларов в месяц, до 500 - 17 долларов, до 2000 - 60. Причем органичение не жесткое, если превысите, придет письмо - не хотите ли поменять тариф. Если выберите этот вариант могу попросить у них промокод. Уже давали, но помоему он закончился.
Оба варианта можно пробовать на отдельных небольших по количеству почт доменах и сравнивать.