What about an SMTP proof of work extension? Smaller SMTP relays that would typically have a harder time sending mail could opt in to solve a problem to increase the chance of delivery. The difficulty of the problem could be inversely related to reputation.