Thanks for pointing out the IMAP approach. I use IMAP on my phone but never really considered using it download all my mail.

I'll give offlineimap.org a look..

To answer your other question, I have 20k emails because Gmail doesn't delete by default, so I just archive as I go..

I'm a zero-inbox type so I use labels and searching a lot. Those 20k emails are surprisingly well organized..