Maybe it is time to see about creating an Internet Standard for ways of expressing "postage" or other distinguishing features of non-spam email.
I could envision a new class of email, "high-value" or "high-priority" email. Eventually, virtually all non-spam email would migrate to this category. Sending high-value email would impose some costs on the creator. This could be in the form of "postage" as we discussed, or it could be the result of a high-cost calculation like the cryptographic hash collisions proposed by Adam Back, which I described earlier.
(I believe the latter has a number of advantages, as it does not require
an electronic payment infrastructure, and there is no danger of the wrong person stealing the "postage", hence no need to encrypt the message, and no requirement for an elaborate public key infrastructure.)
There could be multiple classes of this email, with each one taking an order of magnitude more cost to produce. As technology advances, people could ratchet up their mail filters to require higher value mail.
The standardization effort would define algorithms for creating these high-cost fields, and mail headers and formats to represent them. Then it would be a matter of publicizing them and getting software authors to implement them. It would be best if one or more email vendors were involved with the effort from the beginning.
Internet Standards are the responsibility of the Internet Engineering Task Force (IETF). I looked over their working groups and didn't see any existing and active ones which looked appropriate for this kind of effort. There is a group on "responsible use of the internet", but their charter is just to produce advisory documents about spam, not to define new mail formats. You can read about them at http://www.ietf.org/html.charters/run-charter.html.
I am a co-author of an Internet Standard, RFC 2440, which is about PGP, the security software I work on. Most of my input was technical and I didn't get too involved in the political/adminstrative work. Probably the next step will be to put out feelers to various interested parties.
If anyone knows of any existing efforts along these lines, please let me know.