O protocolo POP3 não possui nenhum método para rastrear quais mensagens são lidas versus não lidas. Essa é uma funcionalidade geralmente implementada no cliente.
Por exemplo, no Outlook 2007, clicando no botão "Mais configurações" na janela "Alterar conta de e-mail", é exibida uma janela "Configurações de e-mail da Internet". Nesta janela, sob a guia "Avançado", há uma opção para "Deixar uma cópia das mensagens no servidor". Quando esta opção está ativada, o cliente não apaga as mensagens após o download. O cliente mantém uma faixa local de quais mensagens foram baixadas.
Então, quando você muda de cliente, esse processo de rastreamento local começa de novo, daí os milhares de e-mails "antigos" sendo baixados.
É uma limitação do protocolo POP3, então não há muito o que fazer. Se o provedor de e-mail também fornecer um serviço IMAP, você poderá considerar a mudança para ele, pois esse protocolo pode acompanhar a leitura e a não leitura no servidor.