I thought paperless billing was a good idea until I stumbled across similar situations. I now try and ensure I keep paper billing as much as possible (or at least have them e-mail me a bill every month where I can back it up myself).
2 years should be a legal minimum for free, open access to bills, because many self employed people only do their accounts once per year and you get nine months in which to complete them.. so that's 12 + 9 == 21 months you have a legitimate need to collect together your records.
I switched to paperless with HSBC and their statements go back 6 years, it was one of the "features" of going paperless. Switching back to paper the 6 years were still there :)
I've switched back and forth between both methods though, but they are good enough to give me free statement prints going back 6 years whenever I request them.
Doing your accounts and collecting together records at a single sitting is more efficient than remembering which provider restricts access to your records at what times and having to collate documents at different times in the year to compensate, IMHO.
Even better though is to just use revert to paper billing to avoid all this BS which I consider even more efficient (for me) than having to log on to services to print out receipts.. or the technique blibble mentions below to request the provider sends you every piece of personal data they have for a single fee ;-)
It is an interesting dilemma really. Should one really try to retain inefficient people as paying customers or will add to customer support and techincal debt later on. Something to think about.
2 years should be a legal minimum for free, open access to bills, because many self employed people only do their accounts once per year and you get nine months in which to complete them.. so that's 12 + 9 == 21 months you have a legitimate need to collect together your records.