«Скачивает заголовки заново» — значит протокол POP3.
При POP3 подключении клиент хранит базу писем у себя (или только заголовки, как настроено) при этом индексация идет по номеру сообщения на сервере. При смене сервера — сменилась и нумерация, соответственно клиент считает что письма новые, так как таких номеров в локальной базе нет.
Обычная практика использовать IMAP доступ — когда письма хранятся на сервере (и еще много других плюшек, в сравнении с POP3) — это сильно упрощает миграцию.