At this stage of PKI deployment we've figured out how to issue certificates and evaluate them in a reasonably interoperable manner but not how to revoke them. In fact, when it comes to revocation, we can't even agree on who should do it, how it should work or even what it means.
In the most literal sense, to revoke a digital certificate is to UNDO a persistent signed statement. Revocation doesn't sound controversial or, at first glance, even very hard. At the root of the problem though is the maturity of the technology itself. While the concept of digital certificates has been around since the late seventies, only now do we see any plans by commercial certificate authorities and enterprise PKIs to issue them on a large scale. And as technologists, we've done a terrible job of explaining certificates and digital signatures.
Viable trust models already exist that do not include explicit ``identity'' certificates, most notably PGP (``Pretty Good Privacy'' [2]). In key-centric PGP, key holders are responsible for notifying their correspondents of a key compromise -- a form of self-revocation. After all, key compromise is what they should care about; for it allows the crook to impersonate them in a transaction. We do not tend to think of the subject of a certificate being able to unilaterally revoke that certificate, but that's exactly what is necessary if the subject knows its private key has been compromised. Key holders could ``bulk'' revoke all their certificates acquired with the same key through some kind of registry. This is a natural analog of credit card registries with the convenient side effect that multiple certificates issued against the same key establish an alias: Bfox@microsoft.com can easily become barb@skijump.com when two certificates are bound to the same key pair.
To make this phenomenon clear to consumers of public key systems including application developers and end-users, we first need to position certificates as merely evidence for a decision that the certificate acceptor needs to make. The certificate (or a chain of them) is intended to provide enough information for an acceptor to determine whether he will accept the bound signature for a transaction, period. Confusion arises however because actual certificate evaluation is usually buried deep under the covers in some application or system. Most Internet-savvy users understand the concept of trusted root certificates, which are usually either ``baked into'' or installable in their browsers, and that a digital signature/certificate chain ending in one of these root certificates constitutes validation. Revocation, however, is a different matter -- because it doesn't work yet. In other words, there's still time to make revocation make sense.
So far, though, we've manage to confuse certificates, which are solely intended to establish transitive trust through public keys, with lots of real-world analogies like driver's licenses and credit cards. In retrospect, this was probably a bad idea because many of these examples lose sight of the function and value of the signature key. The long-term cost of these false similes is that before revocation can make any sense we have to start over in explaining certificates themselves.