As everyone else has alluded to, IMAP is actually a better match for what you do that POP3. I have several gig of email on my IMAP server (about a gig of mine and the rest other users). I access it from my phone, Thunderbird, Outlook and webmail.

If you end up running you own server, whatever you do make sure you don't end up running the UW IMAP server. Courier IMAP is good, but maybe a little unnecessarily complex. I use Dovecot which is easy to set up and performs very well even on very old hardware.

Also, using Dovecot you can get away with sticking with mbox style mailboxes due to Dovecot's excellent indexing system. My multi-gig IMAP server is a lowly PII 400MHz with only 386MB of RAM and moving/deleting within several hundred meg mbox files is pretty immediate.

While maildir helps with performance, it does complicate things like incremental backups, due to the way it moves files around and changes their names when their associated message changes state.

I am tempted at the moment to move to GMail hosting for my mail.