To institute an optional charge for sending e-mail, let us say 1 cent per message.
The amount is not significant for real communication, but is enough to make spam business unprofitable.
The charge is applied by service providers and is carried as digital cash in the message header. Message sender has per-message option whether to pay this charge or not. If he pays, provider includes digitally signed header saying the charge was paid and digital form of the cash drawn on sender's account.
On the receiving side, the header is analyzed and is either accepted as trusted or rejected by receiving host using conventional certificate chain authentication technologies. Individual message recepient has (1) global option in account preferences whether he wishes to receive unpaid mail; (2) filter of addresses or zones that may deliver unpaid messages (i.e. known friends or relatives or other trusted senders).
If the message is rejected, it is bounced back as undeliverable.
If it is accepted and is not designated by the recepient as spam, the charge is credited back to the sender.
False header generation is persecuted along the same lines and existing laws as financial/credit card fraud.