Search is IMO the hard part. I know you can do Lucerne, but getting that working well with email is hard. Until recently Outlook's search was crap compared to gmail. too, and mutt is still essentially "headers only".

Still, shouldn't be that hard to do as long as it is your own server and you trust it; I imagine a lot of the difficulty of gmail is scaling, and even a single user with 20-50GB of mail isn't in the same league.

If you were to outsource it to a service provider:

I'd love a way to do privacy-protecting search on my mailbox, either by building/maintaining a local index, or even more amazingly, some kind of cryptographic/data structure magic: do processing once either pre-encryption or on the local device, then add it to an index, with a configurable slider for data leakage vs. search quality. Search could execute locally and remotely.

(This is to allow you to use webmail with no local persistent storage, or a new phone, to search your email on a server, without trusting the server).