The EU has a lot of laws regulating the privacy of personal data which tell companies when, how and under which conditions they may store information about their users. GDPR is the most notorious of them and is estimated to cost companies billions of dollars over the years.
But why couldn't it be solved through a different angle? Instead of requiring companies to handle personal data with more care, why not require that they allow anonymity when using their services? For example, airlines/trains/buses could be required to transport passengers anonymously within the Schengen area. Postal services could be required to give out packages to anyone knowing a secret code, rather than based on identification documents. Banks could be required to issue cards with a fake name printed on them, so that one could pay online without disclosing their true name. Given the option to use an anonymous identity, storing personal data with care would become much less important.
This would solve the issue with more of a free market approach - anyone who wants to stay anonymous, will stay anonymous. And those who don't can give out their real name. Is there a critical flaw in the proposed approach? Or perhaps the EU has already considered it?