The key is "locked phones they sell for cheap". Gotta be paid for somehow.

You can buy an unlocked phone easily; I got mine at eXpansys. Be prepared for a shock if you don't know what a phone actually costs...

What you got by paying full price was a network-unlocked phone but it will still be locked when it comes to the software running inside it. Unlocking so you can run your own kernel will void the warranty.

If all you want is a root shell to the existing software, "Universal Android Root" seems to be the tool to use and won't void your warranty. It's still a hack and not something you get out of the box.

The only phone I know of that actually seems to come unlocked is the Nokia N900 where you can get a root shell out of the box and probably also swap the kernel for your own without voiding the warranty (not sure).

Universal Android Root seems to be the best answer for now. It's as easy to install as any non-market Android app. Of course, it may get disabled by OTA updates.

Barnacle seems to be the wifi tethering app of choice, as it's free and works on almost any hardware.

I'd really like to see Google start using their certification process to stop telcos from pulling this crap. Data is data. You're a dumb pipe. Get over it.

It's very easy to buy unlocked phones in Germany and, from what I hear, most of Europe. Even data roaming prices within Europe have come down to very agreeable levels. I'm with O2 Germany, and IIRC I can use data roaming anywhere in Europe and never pay more than 60e a month for it, which seems very fair to me.