I beg to differ about phones purchased from AT&T. I think several folks here who have purchased theirs from AT&T said that theirs were locked despite the fact that the paid full retail price as opposed to subsidized.
My guess is that whatever Apple ships to AT&T, the IMEI numbers get entered into "locked" database even before they are actually sold to end users, all AT&T does it tie them to accounts during sale.
The phones that ship to Apple retail stores are different story though. Given that same unit can be activated with either AT&T, Verizon, Sprint, or sold as Device Only, they are not added to any "locked" database ahead of time. Those activated on a contract are added to that "locked" DB at the time of sale, Device Only remain unlocked. That is why 4S boxes/packaging no longer contains any carrier-specific logos/branding as all other iPhones before that did. The sticker on the bottom of the box does list the ICCID (SIM card number). I have seen some screen shots on eBay of boxes from unlocked 4S, and ICCID info was missing. I suspect that those that go on sale here in the US will be the same way as well.
So going back to what I have said before, if you want the unlocked one, I would stay away from AT&T stores as you will probably end up paying full retail price and will still be stuck with locked phone. The one purchased from Apple though would in fact be unlocked as was the case with many others (myself included).
----------
I just did that. Actually tried to change to the 4S plan online, but it wouldn't do it because their billing system was still showing my old 4 and kept saying that the 4S data plan was incompatible with it. Called them and they added my 4S IMEI to their system and dropped that of my old 4 and I was able to change plans then.
P.S. After they added my IMEI, I tried swapping in my pre-paid T-Mobile SIM into it and it still connects and is able to make and receive calls. So for those who are worried, my 4S is still unlocked despite AT&T now officially knowing that I use it and has its IMEI in their system.
The last part is VERY interesting....Im curious to know if you try restoring in iTunes now, after ATT put your IMEI # into their system, whether iTunes will "take you out of" Apple's Unlock data base at time of restore....feeling lucky?? LOL