Firstly I don't have a credit card but in saying that, my debit card statements are all issued online through the bank's own website!
Think I now also have all my bills sent via email. I just realised with my last power bill that it was costing me something like $1 to have them post it so I changed to paperless. Ironically one of the reasons they give for going paperless was, funnily enough, to save paper but when you switch over online the first thing it asks is if you want to print the confirmation.
I have seen that sort of requirement a number of times, and never been asked to produce them.
I was asked to provide a copy of my council tax bill when I applied for a parking permit. We have an exemption, but they happily accepted the one that showed my council tax as 0 pounds. The rest of the statement went on to detail how the tax would have been spent, had I been required to pay.
I suspect the requirements are there so that they can refuse service to someone they just don't like and then just point to missing documents to justify it.
I had to do something similar in Bendigo a few years ago. I printed my bank statement in colour and folded it into thirds.
I suspect Cristina's hit the nail on the head. I've also occasionally suspected that imposing ID requirements that foreigners can't meet is one way for a business to discriminate without breaching anti-discrimination laws (once in the US I encountered a business which would only accept a driver's licence from that state as ID).