In this paper we present a certified e-mail system which provides fairness while making use of a TTP only in exceptional circumstances. Our system guarantees that the recipient gets the content of the e-mail if and only if the sender receives an incontestable proof-of-receipt. Our protocol involves two communicating parties, a sender and a recipient, but only the recipient is allowed to misbehave. Therefore, in case of dispute, the sender solicits TTP’s arbitration without involving the recipient. This feature makes our protocols very attractive in real-world environments in which recipients would prefer to assume a passive role rather than being actively involved in dispute resolutions caused by malicious senders. In addition, in our protocol, the recipient can be stateless, i.e., it does not need to keep state to ensure fairness.