Here's a solution. Tell spammers that, if they get a cryptographically signed contract from the company, they won't be fined as badly. Of course the company will be fined far worse, but if the spammer is caught without said contract, the entire burden falls in the spammer's lap.
Of course then the only problems in front of us are (1) keeping the keys private, and (2) that minor problem that the entire world isn't under the same government. But I'll leave those issues to the reader.