Опубликовать сервер наружу, прописать соответствующие A- и PTR-записи (SPF, DKIM, DMARC - по возможности), а также вторую MX-запись с большей стоимостью.
Проверить работоспособность системы с помощью
https://testconnectivity.microsoft.com/tests/exchange и
https://mxtoolbox.com/.
Если всё нормально, понизить стоимость MX-записи нового сервера, чтобы она была ниже, чем стоимость старого.
Подождать пару дней и последить, как ходит почта.
Если всё нормально, убрать DNS-записи провайдерского почтаря.