The regional carriers, not the big ones. Anyone that doesn't have the iPhone "legitimately" will allow you to use it like any other phone on their network.
T-Mobile lets you use the iPhone with whatever plan you choose. I don't understand why he didn't notice that, given how huge they are. It's understandable he wouldn't have thought of the smaller ones.