Search index could be protected to some extent by using a bloom filter.

This way attacker could only recover unordered list of dictionary words that were in the message and the list would contain false positives (they could tell whether you write love letters or bomb threats, but couldn't get your password reset URLs).