The Nokia phones are all compatible, but what you are seeing is a limited selection of phones being offered by T-Mobile. I'm certain you can buy whatever phone you want to use with the T-Mobile Web'n'Walk Plus service, providing it supports Bluetooth (DUN or PAN, but currently only DUN is supported by N800s while PAN works fine with Windows/Mac laptops).

Three offer a £5/month data tariff but it's not (officially) permitted for use with "laptops" (aka tethering), however I've heard they turn a blind eye to this usage so you might be able to get away with it (the same could be said for the standard Web'n'Walk £7.50/month on T-Mobile).

Beyond the £5/month offer on Three, T-Mobile have the best data tariffs in the UK particularly if you want to abide by the Ts&Cs.

As for phones, buy a SIM free (most Nokia and Sony Ericssons, not sure about Samsungs but avoid Windows Mobile phones as they don't support BT DUN). Or negotiate a better phone from T-Mobile - the MDA Mail is not the only phone supporting their data plans, try a N80 or N95. Make sure you get a 3G/HSDPA phone though, you don't want to be stuck with GPRS!