Apple can unlock it remotely if they want. Not a problem at all. Whether a phone is locked or not depends on it's status in a database administered by Apple. Either the operator or Apple can change its status from locked to unlocked. Once the status has been changed to unlocked, it will be pushed through to the phone via iTunes.
When you buy an iPhone in Europe, you can buy it unlocked or locked through an operator. Many operators are obliged to unlock the phone after the contract expires or even straight away. They do this by sending in the IMEI # to that database. The phone you buy unlocked already has a status of unlocked in that database.
In principle, AT&T could unlock all their phones if they wanted to. They just don't. If you're a tourist and bring a foreign iPhone to an Apple Retail store and for some reason you have it exchanged due to issued covered by the warranty, you can have Apple unlock that phone as well. They usually only know about this in the bigger stores ie Chicago, San Francisco, where the big tourist crowds show up.