Since verifying the entire message amounts to resending the entire message, it should be possible to simply extend the mail servers to allow one to call another and verify by asking about the sending address, the receiving address, and some small digest representing the message. A typical way of calculating this digest could be a hash of the actual subject line.