Honestly, I think all phones should be sold unlocked.
I use T-Mobile and they've differentiated themselves from the other major phone companies by offering two types of monthly service/handset combos. Either you get discounted handsets on locked-in contracts, and they're traditionally priced slightly higher per month, or else you can buy a phone for MSRP and either pay all at once, or else spread it over the next 20 months' billing cycles. The monthly service with this approach is between $10-20 a month cheaper, too. Also, if you have a GSM phone, you can walk on with it and just buy service.
I can understand why cell phone companies lock the handsets for people in contracts since the cost of the phones is subsidized. If, however, you're buying a phone for retail price and using it off contract and just using a "monthly plan" or even just buying it as a "spare" *cough cough, using it on another network, cough cough* you should have the option guaranteed that you can have the phone unlocked at the store when you buy it. Also, once your contract is fulfilled, they should allow the same thing.
This would open companies to competing solely on the basis of quality of service, since if you wanted to buy an HTC HD2 and use it on AT&T or buy an iPhone and use it on T-Mobile, Use the Incredible on Sprint (or even Metro POS) or get an EVO 4G and use it on Verizon, YOU COULD!!!