Who would get this money? I agree that it needs to be some solution involving a cost, given that most of these companies have shown multiple times that profit isn’t just their main concern, it’s the only concern.

Think of it like a class action lawsuit on behalf of investors. Instead of entrusting their savings to a company, people are entrusting them with their personal information. If there is gross negligence on part of the company leading to that data being leaked then all of the people whose data was stolen should be able to claim monetary damages. If a legal precedent is established so that these claims can be pursued whenever this happens it should provide enough motivation for these companies to take preventative measures.

The government typically... who might in turn do something like a tax rebate (write a check to everyone, ontario has been doing with the carbon tax) or just stick it into the general pool of taxes (reducing everyone's taxes).

So the American government gets a cheque for every other nations citizens that use FB, or FB has to determine where each of their users reside?

Respectfully, I'm not sure either of these lead to outcomes we want

Sounds interesting. Shall we call it "GDPR"?

Honestly the EU need to finans a organisation to deal with GDPR violation, hell it could finans it self. The GDPR is the single best piece of legislation ever written, in term of privacy, but enforcement is lacking.

They already do. The Data Protection Commissioners in each state are growing rapidly to try and tackle the volume of work.