Speaking of T-Mobile and Web'n'walk, I got Web'n'walk and a Vario II last year. The Vario II being less than useful, I eventually sprang for an unlocked Sony-Ericsson M600i and stuck the sim in it. The M600i has one or two quirks (don't use it as a clock!) but it's a decent phone and it works fine with the N800.

(The one thing to remember is that HSDPA phones eat juice like there's no tomorrow. The M600i can manage almost 60 hours on standby, compared to about 30 hours for the Vario II (aka HTC TyTN); but switch the M600i to GSM/GPRS and it'll go for a week. In actual connect time, you want to make sure it times out after only a couple of minutes, or you'll find it's only good for 2-3 hours before you're hunting for a charger.)