> If you have to customize the client anyway, you might as well encrypt the metadata.
Yes, but then you'd need a custom extension, whereas the proposed setup would be covered by, e.g., Enigmail for Thunderbird. Depends on the userbase / use case - if one were to set up such a system for themselves, then yes, this would be nice.
> It looks like you can use an unmodified IMAP server -- your MTA would encrypt each mail part individually and your mail client would decrypt.
Yes, that's the plan :) No need to modify the mail server itself.
> The sticking point is server side search, which is available in IMAP4. You'd either have to skip that, or implement one of the search over encrypted data algorithms (which are rather slow).
That is true, and this would indeed involve writing custom code/extensions. Normally, email subjects are not encrypted / presumed 'public' (in a sense), so one way to do it would be to simply allow searching for email subject lines, which would not be stored encrypted on the server. Not sure how much customization server-side this would require.
edit another way to look at it would be, it shouldn't be possible to do any kind of search on the server. The client (which would presumably actually store all the mail archives (e.g. in an encrypted container which could be hooked up to a simple automatic offsite backup solution)) would do all the search. Again, however, depending on the setup, this might require some customization.