The notmuch mail client

if you use a good IMAP server (like Cyrus) you can have fast text searches, arbitrary labeling of messages, but not have to have everything stored locally on each client machine that you use (so that you could access it effectively from a lightweight client on a slow network like a phone)