Bem, você já disse que o único mecanismo de conexão que você tem é o POP, então é só isso que vai estar disponível. Existem algumas ferramentas desenvolvidas para fazer migrações POP em massa de dados quando você tem uma tonelada de caixas de correio envolvidas para reduzir o trabalho manual, mas com apenas 5 contas, provavelmente não pouparia muito tempo.
A única outra solução óbvia é ver se a empresa atual está disposta a despejar os dados em DVDs ou algo para você. Alguns hosters farão isso por uma taxa.