1. A method in a computer system of a recipient for processing communications based on reputation of senders, the method comprising: receiving from a sender an initial communication addressed to the recipient, the initial communication including a public key of a private and public key pair; verifying whether the initial communication was signed by the private key corresponding to the public key without verifying via a public key infrastructure whether the public key is a registered public key of the sender; upon verifying that the initial communication was signed by the private key, determining desirability of the initial communication by receiving from the recipient an indication of whether the initial communication is desired; establishing a reputation based on desirability of the initial communication; and associating the reputation with the public key; receiving a subsequent communication addressed to the recipient, the subsequent communication including the public key; verifying whether the subsequent communication was signed by the private key corresponding to the public key without verifying via the public key infrastructure whether the public key is a registered public key of the sender; and upon verifying that the subsequent communication was signed by the private key, adjusting the reputation associated with the public key based on desirability of the subsequent communication; and processing the subsequent communication based on the adjusted reputation associated with the public key.