If companies stored customer data encrypted by keys that are held by the customer, they wouldn't have this problem. Furthermore, they wouldn't have to worry about deleting customer data either. The customer would have the power to simply deny access to the keys.
But Google needs to know my search query to be able to serve me a results page. Google will know my phones location if I use their WiFi-positioning-system. Google needs to know my address and payment information to have me buy apps.
Encryption can not help me here. I need to be able to trust Google not to collect that data without my consent, that they do not store that data longer than needed to provide me the service and that they do not share that data with anybody that has no right to it. That can only be guaranteed by laws.
This is about laws, and the need for such laws will not go away by encryption alone.