I'm assuming you're using IMAP to access the provider (since, if you were using POP3, you wouldn't really be storing mail on the provider side) since you describe yourself as having "mailboxes".
If you're just using POP3 then nothing is being stored at your provider. You can transition over to the new hosting company (shortening TTLs on DNS records with an exponential backoff, etc) and start receiving mail from their servers.
Continuing on the IMAP mailbox front, thought:
If you've just got a couple of mailboxes you may want to consider just using your email client's built-in functionality to "archive" items to a local store and them manually "copy" them up to the destination server. How that'll work will be client-dependent (Outlook can export the whole mailbox to a PST file for later import, etc).
I'm going to throw in a good word for imapsync. I've used it in a couple of migration situations and I've been very pleased with it. You can run imapsync under Windows with ActivePerl, or under any *nix OS w/ perl. It's well maintained and, if you want, you can even purchase commercial support.