Você precisará acessar seu e-mail por meio de uma conexão IMAP para fazer isso. A menos que haja uma opção de download de arquivamento específica oferecida pelos clientes de webmail (e eu não estou familiarizado com nenhum, exceto o squirrelmail), essa é sua única opção AFAIK. Se o provedor oferecer apenas POP, então, pelo menos, você poderá arquivar suas mensagens, mas não poderá importá-las para o novo servidor, a menos que ele ofereça suporte ao IMAP.
Descubra as configurações de conexão do seu provedor e configure o Thunderbird ou o cliente de sua escolha. (Eu faço isso no Apple Mail rotineiramente.) Com o IMAP, apenas copie as mensagens da pasta em seu servidor para uma local no cliente, reconfigure o cliente para o novo servidor e, em seguida, copie-as de volta.
Com o POP, é um pouco mais estranho, já que o protocolo é unidirecional. Talvez seja necessário fazer alguns ajustes no cliente para fazer o download de todas as suas mensagens antigas, mas, ao fazer isso, você terá pelo menos um arquivo local.