Petmail is a permission-based anti-spam replacement for SMTP, using recipient-defined CAPTCHA challenges for new senders, automatic (but revocable) permission-granting for most correspondents, encrypted and signed (but pseudonymous) messages, and provisions for easily changing addresses or transports (including a mechanism to publish remailer SURBs as a destination).
The summary: all messages are encrypted and signed. Messages from known senders (those who are in the recipient's address book) are accepted according to per-sender policies, which can limit message frequency, size, and content-type. Mail from unknown senders must include a Ticket obtained through a CAPTCHA challenge to be accepted, which serves to rate-limit new correspondents. Permission is automatically granted to recipients of outbound mail, and can be extended by third parties who already have permission. All permission to send mail can be revoked at any time by the recipient.
I started developing this system in June 2003 because of concerns I had with several anti-spam proposals floating around the net at that time. Most that I've seen either fail to solve the real problem or involve significant identification costs, which needlessly increases centralized control over the mail system and takes a heavy toll on anonymity.
The design paper describes the architecture and philosophy. The original protocol outline is located here (version 1.7).