Project Cess Pool needs to come back
A company has 2 million records, interspersed with 10 million fake records, and some encrypted method to tell them apart.
Virgin Media planned this when the government said it wanted everyones internet history flowing to a government server.
They were going to FLOOD the logs with fake data. Legal because their system WOULD visit aaaaaaa.com aaaaaab.com etc for a microsecond behind the scenes.
Or give users a way to click an icon at night to run such a randomized search.
The other option is to ramp up security so ALL data is encrypted to 2048bit standard. Decryptable one-by-one using the companies software which is customized ONLY for their hardware in some unique way, such as requiring specific co-processors to be accessible. Because the co-processor does XYZ to the data as it goes through, and doesn't perform any calculations that can be copied off, it becomes impossible to just steal valid data en-masse.
You'd have to steal ALL the data AND build a physical identical replica of their data servers to decrypt stuff.
The final way is "beat them at their own game". basically pump data online of fake customer details. So many that you can't tell whats real.
Films have started doing this. releasing HUNDREDS of fake spoilers, so even if you find a real spoiler you'll probably forget it and ignore.