Off the top of my head, I think it was easier in France (although this was 16 years ago), Iceland, UK. I also recall it being easy in Aus/NZ. Fairly easy in the US as well, I believe, but as I'm a resident, I don't think too much about what address to use when having a prepaid SIM shipped to me, nor do I ever expect to have to show my papers for something like this. (although, of course, a postpaid account usually involves a credit inquiry, so ID docs would be used privately, not for government reasons, for what that's worth).