Я бы действовал примерно по такому плану:
1 настроил новый почтовый сервер на linux, что именно выбор за вами: своя сборка postfix,dovecot,mysql,rouncube,postfixadmin или какойто готовый комбайн типа zimbra.
2 на новом сервере создал бы ящики такие же как на старом сервере.
3 заранее при помощи утилиты imapsync или аналогов залил бы основную часть почты в новый сервер со старго сервера.
4 в день Д (например на выходных) обьявил бы тех работы, переключил входящую почту на новый сервер, и дозалил темже imapsync дельту писем пришедших после предыдущей заливки на новый сервер.
5 готово - старый сервер уже не у дел.