Mike Ingle says: There is no way to know now when a key was sent to a server, so it is hard to know when to delete it. One way would be to keep track of when new keys are sent or updated, and delete any key which has not been updated within a certain time, such as one year. All existing keys could be given six months to live. Those who wanted to keep their present keys could send them again, and others could create new ones. <- Why not a note sent from the server to the key address to the effect: Your key has been deleted.... etc. Not only will this fish out some of the changed addresses and thus non- updated keys, but also remind the legitimate user who just hasn't gotten or looked to get a new signature in 6mos - Years to think about a new key and a revocation. I assume revocations will be kept for good?