As security enhanced systems for standard e-mail, certified e-mail schemes guarantee the fair exchange of a digital message with the corresponding receipt between two mistrusted parties. That is, the intended receiver gets the e-mail content if and only if the e-mail sender obtains an irrefutable receipt issued by the receiver, which could be used to prove that the message has been delivered to the receiver. A number of such protocols have been proposed in recent years. However, most of them are not suitable for mobile networks, since many intricate cryptographic primitives are involved so that considerable overheads are introduced. In this paper, we present a novel simple protocol for certified e-mail delivery. Technical discussions are provided to show that our new solution is both secure and very efficient so that it is truly suitable for wireless mobile users, where the available devices usually have limited resources on computation, communication, storage, and power supply.