Dear lazyweb: I am in a dreadful situation! I need to secure e-mail communication between five types of users:

Outlook 2003 users who receive their mail by POP3 from Exchange,
Thunderbird users downloading mail with POP3,
Apple Mail users downloading mail with POP3,
Webmail users (Squirrelmail and Roundcube),
and a bunch of Unix folks using proper clients.

To make matters worse: there is no common provider or server infrastructure, so the solution must work across providers and mailboxes.

Requirements

Human error should be anticipated and prevented.
Mail between all parties must be encrypted (and signed) automatically. If encryption is not possible, the mail must not be sent. This includes the situation where not all mail recipients’ keys are known;
Ideally, one can define rules (using wildcards or regular expressions) to enforce certain policies.
Mail to other parties may be signed, and it would be good to be able to turn this on and off by default;
The MIME standard should be employed so that the mail body is not altered, and attachments can be seamlessly encrypted too. Existing MIME parts should be encapsulated as children of a new multipart tree;
Incoming mail should be automatically and seamlessly decrypted/verified, and the user must be alerted if the verification fails.

Ideally, the solution will be open-source. However, if proprietary software performs better, then we will gladly use that where required.

Previous attempts

So far, we’ve tried (and were let down by)

GpgOL, which has very irky and brittle integration with Outlook and can only do inline signing/encryption.
S/MIME, which seems supported by all involved clients, but Outlook does not really allow you to specify policies. Encryption seems to be opportunistic at best, which is not enough.
GPGrelay, which is promising because transparent, but apparently messes with MIME, and I am unsure whether it can fit between Outlook and Exchange. I have yet to run real tests though. If you are a GPGrelay user, or you’d like to try it (it’s Windows-only), please get in touch.
WinGEAM, but that apparently no longer exists, and neither is the underlying GEAM.

Help!

Does anyone have proper suggestions over what to use?

In fact, if you are interested in devising a solution, or even deploying it, there’s money to pay you for those services. Write in if you are interested.