Methods and systems are provided for a cancellation server maintaining a database of identifiers of cryptographic puzzles. A cryptographic puzzle is created from a unique identifier and a timestamp, and is attached to an electronic mail message, along with the puzzle's solution. The recipient verifies that the solution is correct and that the timestamp is current, and further queries the cancellation server with the puzzle identifier. If the identifier does not exist in the database, then the recipient knows the received message is legitimate. If the identifier already appears in the database, the received message can be automatically removed from the recipient's computer.