With regards to search, I recently installed Cyrus Squatter for full text IMAP searching and it is blazing fast. To me it seems just as fast as any of the special case local searches I've seen people build (Spotlight/recent Thunderbirds).
Any new mail storage protocol should anticipate the need to store encrypted messages at rest. Sure, it can play a part by storing an encrypted index on the server to deliver to authorized clients, but all decryption and index updates should take place client-side with the user's private key. Stable UID's can help make this a reality. There is no reason to store messages in plaintext on the server, and no new protocol should depend on it.
