You're describing proof of work, not blockchain. It's easy to implement it without a blockchain: make MTAs require the hash of the enveloppe of the mail (+ a no

You're describing proof of work, not blockchain. It's easy to implement it without a blockchain: make MTAs require the hash of the enveloppe of the mail (+ a nonce outside the enveloppe) to start with a certain number of 0 bits. And make the MTAs return a parseable message when there aren't enough zeros, so the sender MTA can retry with other nonces until there are enough zeros. And the enveloppe already contains a Message-ID which is to be unique (as it contains the hostname of the sender) and unpredictable, so there shouldn't be issues with replay attacks.