The phone need not be unlocked (well, unless it's locked to some other network), debranded, or hacked, because T-mobile does not care if you tether. Any phone supporting BT DUN (or presumably PAN, but I haven't tried that yet.)

I've got a Nokia 3555b (from T-mobile, stock) and the N800 figured out (i.e. was preconfigured with) the right settings for t-zones (which is $6 a month, unlimited, but has restrictive port filtering), except that the proxy IP was formatted wrong (leading zeros break things, evidently) and was defined for http only, though it works for https also.

I've also got a plan to get a (second) battery cover and add an ExpressCard/34 slot, and try with one of these suckers. I have no guarantee this will work with Linux, as I'm coming up short on data for this particular card, but hopefully it shows up (as most do) as a serial port that speaks some extended Hayes commandset, and I can figure it out from there... If not, my laptop's got a EC/34 slot, and I'll find something else to do with the one on my N800.