You just need to encrypt the search index alongside the emails. There are databases that have solved this problem. The hacker's solution would be to put sqlite

You just need to encrypt the search index alongside the emails. There are databases that have solved this problem. The hacker's solution would be to put sqlite inside a truecrypt volume I suppose. Edit: mount it over sshfs if you need end-to-end encryption. And pray that truecrypt and sqlite have optimized their read/write operations well enough.