> Without knowing what was collected how can they prove it was deleted?
They don't need to know what data was collected. GDPR requires you to track all data and mark where you got it from, so the companies are legally required to track this for you, they should already have a switch where they can delete this data at the notice of the user, so they should have no problems honouring such a request from the government.
The government don't know if the data was deleted, but a user will know if a company has data the user didn't agree to give to the company, in which case that company is violating GDPR regardless how they got that data. That wont always come up, but if it does the government will go after those companies.
