I would like to search message bodies of encrypted mails (not "find in current message" but "Quick search" or "search folder..."). I guess that this is quite time and processor consuming on large amounts of encrypted mails but right now finding a mail from someone who encrypts every message is much more time consuming for me...
Adding ideas: There is a vey good thread on Mozilla Thunderbird's bug tracker discussing possibly implementation strategies: https://bugzilla.mozilla.org/show_bug.cgi?id=188988 (with some chaff from users who were unpleasantly surprised that the feature did not already exist) According to this thread, mutt apparently supports searching encrypted mail: http://unix.stackexchange.com/questions/46580/e-mail-client-in-linux-which-allows-to-search-encrypted-mail