"Возможно, взять почтовый клиент (The Bat, Thunderbird) сохранить письма локально, а после смены почтового сервера вновь их подгрузить? "
Возможно. Я так понимаю тут обычный IMAP, или POP. Сливаете почту в pst тем же outlook, и этот pst подключаете к новой почте.