If we are willing to sign a key based on an entity that we KNOW does not really exist, then what does a signature mean?
The key is the identity, period. Let's get that straight up front. Signing a key does not change the identity. Signatures on keys are attestations that the key belongs to some person or email address. Signing a key attests that an identity has a name. I've developed a criterion for signing pseudonym keys. The only party (other than the holder) who can gain any certain knowledge that an e-mail address maps to the holder of a given key is the provider of the e-mail address. In other words, Julf's server should sign wonderer's key. The following applies to any system providing pseudonyms, i.e. mail addresses. The mail server should have a public key. The public key of a user would be encrypted with the server's public key and forwarded to the server. The server would accept as authentication of this public key the same authentication that it accepts for everything else. Once it has the key, it can sign it and return it to the individual, who can then publish it.
Something strange is going on in the word when nym's are signing each other's keys...
The one pseudonym is attesting that they reach the same individual each time they send mail to the other pseudonym encrypted with the public key claimed by that other pseudonym. This attestation is not as strong as person-to-person contact, but as long as the signer reasonably believes that mail delivery system functions as it claims to, i.e. no interposers, the signature does actually mean something. Eric