1. A method comprising: processing an outgoing message using one or more spam filters on a client computer; computing, via the client computer, a result from a proof to be included with the outgoing message that is communicated over a network to an intended recipient when the processing indicates that the outgoing message is considered spam, wherein an extent of processing performed by computing resources used to calculate the proof varies based on the relative probability the outgoing message is spam and the indicated relative probability the outgoing message is spam includes an additional threshold to protect from spam filters that are likely to be more aggressive than the one or more spam filters employed by the client computer; selecting the proof from a plurality of proofs based on the indicated relative probability the outgoing message is spam, such that selecting includes: selecting a complex proof that uses a higher amount of computer resources as the proof when the relative probability the outgoing message is spam is higher; and selecting a simple proof that uses a lower amount of computer resources as the proof when the relative probability the outgoing message is spam is lower; attaching the result from the proof with the outgoing message before the outgoing message is sent to the intended recipient, the result from the proof being included in the outgoing message as evidence that a sender of the outgoing message expended additional computer resources to indicate the outgoing message is less likely to be spam; and receiving a communication from the intended recipient indicating that the result attached to the outgoing message is not enough evidence that the message is less likely to be spam.