To provide this service within today’s Internet I would provide a simple mail forwarding service called PO. PO has light weight financial relations with each participating client. Here is how PO works.
Each client has an ordinary e-mail address known only to PO. Each client also has a unique PO address.
Clients may have special mail software that automates some of the procedures described here. When one PO client wishes to send mail to another PO client he sends ordinary e-mail to PO that includes the message, the PO address of the recipient and an indication of how much postage. We postpone the question of how much cryptographic protection this e-mail requires.
PO knows who the e-mail is from and deducts the postage from the that client’s account and increments the recipient’s account by an amount smaller by PO’s cut. PO then forwards the mail to the recipient at the e-mail address that only PO knows. This e-mail indicates the postage remaining after PO’s cut. PO’s balance with a particular client may be either positive or negative. When it is too far from zero PO sends a check or a bill to the client.
If all messages are signed then we have the non-repudiation properties necessary for third party adjudication. If the client trusts PO then message authentication codes should convince him that unsigned messages from PO are indeed from PO. This requires a secret shared between PO and the client. The same secret can be used to authenticate messages from the client t PO if PO trusts the client. Secrecy is orthogonal although secrecy solutions also provide authentication.
Digital postage may be small and thus require small amounts of trust. Most clients and PO should be at risk of only a few dollars. If PO is well known then it might require prepayment by clients and thus limit its risk to zero.
Client software can keep track of the balance that it should have with PO.