I've just spent several hours scanning and then shredding tedious statements, medical documents and other nasty paperwork. This is even after I've gone paperless with as many companies as possible. Very tedious, not to mention a monumental waste of time and money.
The companies that are paperless vary in what gets stored, for how long and in what format. And if I ever need some statement from years ago I may not even still have an account. I seem to change medical insurance at least twice a year at the moment.
How about a common standard for pushing paperless whatevers out to a third party storage service? These could go directly to Evernote, SugarSync, etc and bypass the post-scan-shred cycle of doom. Just send a PDF, a date, a summary and maybe a service type. Make it easy (or mandatory) to opt in when signing up to each new bank account, health insurer, wireless carrier, etc. Make the world a slightly greener and slightly less boring place.