A Hacker's Replacement for Gmail

I'm not sure why you can't do those things on FastMail.

(disclaimer: I work for FastMail)

Sure we have folders rather than tags, which means you can't add multiple of them to the same message. Probably the biggest lack is that you can't manage IMAP flags via the web interface. Otherwise, our search is now very powerful (since about March this year) and allows you to build filters that show messages from multiple folders in a single view.

Nice stringing together of unixy tools to get this working. I had not heard of notmuch and its related ecosystem (afew, alot, etc.), so that's a useful discovery on my part.

Another relatively painless way to set up a mail server on your own box is http://www.iredmail.org. ( + http://z-push.sourceforge.net/soswp/ for ActiveSync push mail) So far I am fairly happy with it.

Setting up a server in any hosting environment at this point comes with the assumption that its contents can be read at any time by the operators and whoever they let in without you ever knowing about it.

That's still a lot better than Gmail.

Setting up your own mail server is not a terrible woe-inducing undertaking if you have a working recipe to follow and are comfortable with the Unix command line (e.g. http://www.exratione.com/2012/05/a-mailserver-on-ubuntu-1204...).

Organization and categorization are the sticking point features, given what I've seen of most open source webmail applications. But worth looking around. If you have a basic mail server image, you can keep trying out applications on top of it to see what works for you.

Going beyond that to something with a whole lot more encryption and less of an ability for hosting providers to read your data would really require a product dedicated to that end: that is hard to get right.

OP here. Fastmail had 4 out of my required 5 features. I used it for a while. I'm still a paying customer (I paid for a bunch of years). Tags were a deal breaker. It's just not sufficient for how I want to organize things.