That's the easy half. Next, we need a stronger system of domain reputation. For this, we grandfather in all existing domain names, but any newly registered domains need to put up a bond for good behaviour. If one of the big email providers detects high levels of spam from the domain, they can slash the bond, but after a few years of good behaviour the bond is returned.
Of course this gives a lot of unelected power to the big providers, but guess what, they already have that power, except they're using it for making their moat bigger, not for actually solving the problem. If this bond system used a public ledger, then smaller competitors would be able to see the reputation decisions that these big providers made, and crypto-currency would also be suitably international for a global system like email.