An article from CNET, written by security expert Kevin Hanrahan, suggests that instead of throwing out private information to enhance privacy, yet more information should be retained. In particular, he suggests retaining information about access to you information.
The idea isn't new, it is required by the recently-effective Health Insurance Portability and Accountability Act (HIPAA). That act requires that information be retained as well as access logs showing who had access to the data and calling out any strange circumstances surrounding the data. In this way, somebody who suspects that their data was inappropriately accessed could verify this by accessing the logs (through channels, of course).
As with the medical industry, any industries required to conform with this type of policy will undoubtedly complain about the management of such data. However, with storage capacities still increasing at enormous rates and with plenty of folks in the IT industry looking for jobs related to databases and data management, it sounds like a reasonable step to take at this juncture.
The next question would be who keeps this data and who gets access to it. It seems to me that keeping the logging information with the actual data is appropriate, which means that the logs will be in the hands of private companies. This is similar to how HIPAA is currently administered.
As for access, this is a bit stickier. We would need to provide some amount of proof to the organization holding the logs that we are who we say we are. Optimally, some kind of live online system which users can opt in to by providing appropriate identifying information would be the best way to do it.