Proof of work. Every email the spammer sends out would need to be properly encrypted (or else the target wouldn't see your ads). This would actually put a lot of control in the hands of the user - set the amount of work required to mail you through key strength. Spammers would absolutely hate this, it would be like the USPS requiring bulk mailers to prove they aren't spamming by including the recipient name (not "Current resident" or "Our friend at").

Signed messages give you a much easier way to weed out "unknown" sender accounts (=keys). Encryption with signing makes it easier to recognize legit email. You need to go back to decentralized filtering though. Or maybe publicly verifiable signatures (=no sender anonymity) on encrypted content would be an option.