I'm Canadian and just moved to the US. While utilities were pretty good about me not having a SSN (including Verizon), it's all the stuff that comes after that's causing me problems. So many web sites either rely on having an SSN on file, or by contracting to a 3rd party to do identity checks that fail when you don't have a US credit history.

I'm currently in Limbo with my healthcare provider because they won't let me pay my bills online (or set up appointments, see results, or email my doctor) until I validate my identity, I've had to do my auto registration through snail mail because the state's website won't recognize my SSN, and have also had to call other places to get set up on their websites because of having no SSN when I started.

You mentioned T-Mobile, who were pretty good in getting me set up without a credit check, but won't auto debit my credit card when I have a bill. I have to go online each month and pay, with that same credit card. And getting to that point took a couple of phone calls.