It’s not for the faint of heart, but there is now a method to take a new, 1.1.3 out of the box iPhone (including the new 16gb models) and unlock it via software.
Technically you have to jailbreak, downgrade, unlock, upgrade, and jailbreak but it appears to now be possible. The credit goes to George Hotz, who was originally responsible for figuring out the original hardware unlock last summer.
Be careful out there as there is currently no ‘easy’ tutorial (yet) and the usual caveats apply.
UPDATE: Well, that didn’t take long.
UPDATE 2: Looks like ZiPhone is sweeping the internets. PC or Mac tutorials for you! Also check out iphone.unlock.no for a different GUI version. I don’t even care anymore who the original content is on this stuff….so many leech blogs hoover up my posts as well as the tutorials I can’t keep track.