There is more to this problem than how it is that I trust the key. There is also what I trust it for. ... It is hard to see how to record the information about how much I trust the receipent's systems security.

Bingo! This is one of the hard parts of certificate authorities; just what are you attesting to? The American Bar Association has a big document for public review that addresses what this might mean; there are a couple of RFC's that specify CA policies (one from COST in Sweden, I think), and RSA and/or Verisign will give you their policy in hardcopy. In x.509v3 certificates, there is an extensible field where the key-signer can put arbitrary data. The intent is apparently that you put the ISO object-ID (you know, those funny 1.3.2.11.... numbers) of the policy document. There is, of course, no way to interpret the semantics of this electronically. It will be interesting to see how various companies address this issue, for example as they start to support arbitrary CA's in browsers or servers while doing commerce over the web. /r$