I've successfully used the N800 in the UK via a bluetooth phone on Pay-As-You-Go with Orange, O2 and T-mobile. It's very cheap to just get a Pay-As-You-Go SIM from a provider and try it out. Sorry but I haven't tried Three.

In my opinion T-mobile is the best. In an HSDPA coverage area (with an HSDPA-capable bluetooth phone) web pages seem to load near-enough to WiFi speeds. T-mobile pay-as-you-go data is maximum of £1 per day for up to 40 megabytes.

Strictly speaking, the T-mobile tariff is £2 per day for "handset as a modem with a computer", but the staff in my local T-mobile store felt that the N800 was a handheld device, not a computer.

One thing to watch is that some of the operators force you to go through their proxy servers. When using O2, this forced me to get the mobile version of some websites (even though the N800 has a real grown-up web browser). Even with T-mobile, results vary a bit. When I was in Sheffield (on HSDPA), I could only get the HTML version of Gmail whereas in other areas (on 3G) I get the full JavaScript version. However, Google provides a command-line parameter that you can add to the URL to force the real version of Gmail to be used.

I wrote up the connection settings that I used, because it took me a while to work them out myself.