Re: This requirement for paper bills/statements...
much like it seems everyone else around here, i moved house in August. Mostly without too much hassle. There have been a couple of 'prove your address' situations, most memorably, signing up to a new GP, who wouldn't accept my newly updated driving license as proof of address because 'lots of people don't bother to update them'. Fortunately, the nice people in local government are pretty quick to get council tax sorted out, and most places will accept one of their letters as a proof of address.
The thing that really irked me was during the purchase, solicitors asking for 'original copies' of bank statements, which i haven't received for years. And don't get me started on 'certified' ID.....