1. обратите внимание на ответ
hint000, мне кажется, его мнение будет полезно.
Я бы предложил следующий подход:
1. Полная настройка почтового сервера на новом хостинге. (SPF, DKIM, проверка в спам базах и тд и тп) - полноценная. Завести все почтовые ящики, аналогично имеющимся. Добавить в MX с более низким приоритетом. Проверить отправку почты через новый почтовый сервер (получать , из-за приоритетов MX он ее все равно не будет)
2. Подготовка к миграции почтовых ящиков. Хорошо, если есть локальные клиенты (не вебмейл) - часто у них есть возможность архивации, благодаря чему после перенастройки на новый сервис можно все довольно быстро восстановить - подготовить бэкап почтовых ящиков, персонально для каждого пользователя
3. миграция.
Если пользователей немного:
Переключаем MX, почта начинает идти на новый хостинг, но не сразу - часть писем придется ловить в старом и переносить дополнительно. Перенастраиваем почтовые клиенты на новый хостинг. Загружаем подготовленные архивы писем в клиенты.
Если пользователей много - процесс миграции может затянуться. В таком случае для бесперебойной работы необходимо настраивать пересылки между серверами почты, но далеко не все провайдеры электронной почты такое позволят сделать. Еще, если используется вебмейл - с предложенным вариантом архивации старых писем тоже возможны проблемы.
Как можно поступить в таких случаях - варианты есть, но все они потребуют как более широких, чем у вас, технических знаний так и опыта работы с данными сервис провайдерами