First, the complexity of the engine shouldn't matter. You will never get the bulk of users out there to use, or care about, the real power of the engine. They don't want to mess with the engine. The engine should be under the hood, in a black box, whatever engineering metaphor you want. Users just want things that work.
I remember way back when I was at university. There were various absolute rules for good software engineering. The first was that the user should be presented with a must-read manual no longer than one paragraph. Tips and tricks could be more extensive, but that one paragraph was all you needed.
The second was that the user absolutely must not care about how something was implemented. In the case of encryption, I take that to mean, in the case of e-mail, that the engine should not be visible outside of configuration. A supplied key should trigger any behind-the-scenes compatibility mode or necessary configuration to talk to that user. If the keys the user has aren't suitable to correspond with that person, the system should ask if one is needed and tie it to that protocol.
There should be no extra controls in e-mail, except at an advanced user level. If a key exists to correspond with a user, it should be used. If a key exists for inbound e-mail, the key should be applied. The process should be transparent, beyond getting passwords.
Any indexes (particularly if full indexes) should be as secure as the message, good security practices on both will take care of any issues.
Ideally, you want to have the same grades of authentication as for the early certification system, adapted to embed the idea that different people in the web of trust will have done different levels of validation and will be trusted to different degrees. The user should see, but not have to deal with, the level of trust.
Last, GnuPG is probably not the system I'd use. Compatibility cruft needs to be as an optional layer and I'm not confident in implementation.
There should be eight main libraries - public key methods, secret key methods, encryption modes, hashes (which encryption modes will obviously pull from), high level protocols, key store, index store and lacing store. (Lacing is how these are threaded together.) The APIs and ABIs to those libraries should be standardized, so that patching is minimally intrusive and you can exploit the Bazaar approach to get the best mix-n-match.
There should also be a trusted source in the community who can evaluate the code against the various secure and robust programming standards, any utilized theorum provers and the accepted best practices in cryptography. Essentially replicate the sort of work NIST does, but keeping it open and keeping it free of conflict of NSA interest.