Q: How do I remove a key from the keyserver?
A: This is by far the most frequently asked question I receive. Usually what has happened is user has lost access to his secret key and thus the matching public key on the keyserver is now useless. "Lost access" might mean forgetting the passphrase to the secret key, losing the secring.pgp file, or other similar circumstances. Sometimes users want to remove a key because it contains an old, outdated UserID field (for example, the e-mail address typically listed in the UserID field is no longer valid).
Unfortunately, it is impossible (from a practical point of view) to remove a key from the server's keyring. Yes, I can manually remove a key from the server's keyring using pgp -kr, but that is only a temporary measure. Anyone, not necessary you, can upload a copy of your public key to the keyserver. This is convenient because it means if I wish to sign your public key I can download your key, sign it, and then upload the signed key without ever interacting with you directly. The flip side, though, is that if I remove a key from the keyserver at a user's request there's nothing to prevent that key from being resubmitted to the keyserver by a third party. Some keyserver users periodically submit their entire keyrings to the keyserver (often many MB in size) in order to "resync" with the keyserver. Thus, any key I remove with pgp -kr is likely to re-appear in the future.
The only real way to invalidate a public key is to generate a "key revocation certificate" (KRC) and submit the KRC to the keyserver. A KRC is a special type of signature that indicates that your public key has been compromised. PGP won't use a public key that has a KRC attached to it. Generating a KRC, though, requires access to the corresponding secret key, which means that users who lose access to their secret keyring can't generate a KRC. (See the PGP docs for more information on generating KRCs.) I personally recommend generating a KRC *at key generation time* and storing the KRC on a floppy disk someplace safe; that way even if you lose the secret key you still have a KRC you can submit.
So, what do you do if you can't generate a KRC and removing the key from the keyserver doesn't work? The next best thing I can do is "disable" the public key using pgp -kd. Disabled keys remain present on the server's keyring but cannot be extracted; WWW users actually get a warning message if they try to extract a disabled key. To disable a public key you should send a message (preferrably PGP-signed with your new public key) to pgp-public-keys-request@pgp.stupi.se stating which key(s) you want disabled, and I'll manually process the request.
Note that disabling a key is a local operation; that is, disabling a key on every keyserver's keyring requires having every keyserver operator disable the key manually. KRCs propagate automatically through the keyserver network just like signatures, so you only have to upload a KRC to one keyserver. Please allow some time for "disabling" to propagate through the keyserver network.