I'm going through the process of settling here in England, and as part of my visa application they asked for 2 years worth of paper bills (originals only, no copies, downloaded statements or printed scans). "What???" screamed my inner-American. "Who would keep that around?" I had exactly one phone bill sitting around and it was a month old.
Explaining this ridiculous requirement to everybody I could find over here, I was met with nothing but: "Of course. Why would you throw something like that away? I think you're legally obligated to keep all paperwork for at least 3 years. I still have bank statements from the '80s up in the loft." Nobody believed me when I explained that lots of people in the US had paper shredders in their homes.
No sympathy from Her Majesty's Immigration Services either. I stand a pretty good chance of having my visa application rejected as a result of my American inclination toward paperlessness.