I think PGP/GnuPG key signing and exchange customs put too much emphasis on real-world identification, and this greatly hinders the popularity of encryption (and signing). What about virtual/net personalities? What does it matter what some state (or its pawn) thinks is my or anyone else's name and identification number? What does it matter what do people call themselves, or look like? Absolutely nothing! All that matters is that a key can with high probability be thought to originate from a given personality or entity, whether real-world or virtual. Identification papers assigned by some "official body" do not help much there; they can be forged, and if you've never seen the person before, it could be anyone. ID papers are just one signature among others for associating a name with an ID number and a photograph, nothing more. All you're doing when signing a person's key after checking that his face matches the data on some identification paper, is saying exactly that. You're not saying that "this is the key of the author of that and that program or site, or whatever" or "the entity usually appearing with this nick on IRC or using this email address, created this key". But it is exactly that what counts! Instead of meeting a stranger in the real world to sign its electronic ID, the electronic ID should be used to check that the real-world person is infact the virtual personality you know.

If a virtual personality or entity has from its first appereance signed all its messages, software releases – or whatever transmissions – with a given key, then the key can reasonably safely be signed by another entity that has followed this activity from the very beginning, as future proof that it is still the same entity behind any new activity, even after the initial transmissions have been lost. Any man-in-the-middle scenario or site compromise is irrelevant, as anything interfering with the transmissions from the beginning is part of that entity. Likewise, it is safe to sign the key of a real-world acquaintance when the identification information in the key is along the lines: "the person I met when we exchanged keys".

But what if an entity is already known before it starts signing its transmissions or publishing its key? Sometimes the entity can reasonably well be ascertained to be who it claims to be by knowing certain things. An author of a piece of software should know the innards of it like one's own pockets. There's also the option of signing by a proof that the entity controls a given email address or a web site. However, each of these methods are vulnerable to man-in-the-middle attacks, and the site having been compromised after the earlier transmissions. There's simply no way around that. Real-world identification papers are of no help either; they're also susceptible to similar attacks, as is the validity of the key of a real-world acquaintance, if keys are exchanged only after the initial meeting.

A solution is to let key signatures be time-dependent; any association of a time-dependent signature to anything having referred to itself with the identification information in the key before the time of the signature, should be avoided. When a signature on data by the signed key is verified, it should be warned when a time-dependent signature is relatively new. Another option (or a way of looking at the former) is including points of trust in the authenticity of the key in the signatures. As a signer becomes more convinced that the key is authentic, it should sign the key again, to increase its points. This information should be distributed on the keyservers, and is different from the existing level of trust scoring that is local and only measures the trust in the keyholder's signing habits.

Of course, it should usually be avoided to sign keys that could easily be mistaken to refer to some other known entity, real-world or virtual, of which there is no proof that the first entity in question infact is. An email address, however, is quite "globally unique identifier", especially when combined with the time the key was created. Nevertheless, any signatures should be seen as referring to locally unique identifiers: if I have signed some entity's key, and you know me, it is quite likely that any name by which I refer to the first entity, you understand to refer to the same entity. But as the path grows longer, confusions become more likely, and thus signatures – and any references to any given "name" – become more unreliable. This is already the treatment in GnuPG, infact.