Just make sure whatever email provider you use offers IMAP and use a client like Thunderbird to keep a local copy in sync. Back that up somewhere safe and you're fine. If you need good, fast search, use something like X1.
This was something I thought POP did better since it requires maintaining one's own copies after downloading. But it was much less convenient as people used more devices.
Sad that managing our own multi device services is so time consuming.
Data theft is a separate issue. Whether your using gmail, your own mail server or an account with your ISP; if you're machine is compromised all bets are off (including all your other files, not just email). At least with a backup you wont lose your data as a result of the theft.
Sad that managing our own multi device services is so time consuming.