First, a question: how does the government (or any buyer) determine that the data they are buying is genuine?
Second: Assuming that there's really no good way, then there's something you can do. Somebody could simply run lots of ChatGPT style models to generate a flood of nonsense but plausible-looking data about everyone on the planet. Flood the Internet with it. Compile it into lists and offer them for sale. Cheap!
Once there's so much nonsense data out there, then provenance becomes more valuable. It becomes less useful to just buy random data.
Doesn't solve the actual problem of privacy, but it might help in the short run.