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.
How would users verify that the software was working securely? A webmail provider would need to publish a full client-server API and protocol spec, so that you could run some independent software to audit what was being sent to be sure no leakage was happening. This is simply untenable.
Oh and what would really happen is that everyone would lose access to their data since, in general, nobody is able to maintain keys. It's pretty understandable that companies have little desire to redesign their whole systems to provide a crappy experience to a nearly non-existent market segment.