I just bought a iPhone 4 from a Person locally that was AT&T locked.
I put my SIM card in it for a couple of days, then called up AT&T (I am a PrePaid AT&T Customer for the past 1.5 years...just a Backup SIM that I have been keeping active for my trips to USA)...I got through to the regular CS for postpaid accounts because I didnt put in my phone number when the IVR asked me to and went straight on the topic that I want to get my iPhone 4 Unlocked. CS rep asked me for my IMEI and the name of the person that I bought the iPhone 4 from as well as my Pre-Paid number just to check because on their system they can see the IMEI number of the phone currently using the SIM card, Since I emailed the person before purchasing, I had their real name(First name only needed) thanks to their email address so it worked out just fine. My iPhone 4 Unlocked within 3hours.
What you have to make sure is the iPhone 4 and 4S you purchased weren't sold while the iPhone 4 & 4S were/are tied to a contract. If they are still on Contract (the original owner) and didnt do the early cancellation or didnt pay the early cancellation fee then you will be out of luck as AT&T will refuse. But not to worry if that doesn't work out then go to eBay, I was considering eBay had AT&T turned me down.
on eBay they are charging ~$37 per iPhone to Factory Unlock it and I would trust the sellers with HIGH FEEDBACK SCORE especially with 50+ positive feedback for Successful iPhone unlocks, there are quiet a few of them right now on eBay that are doing it, I don't see any reason it would not be legal because if you recall from 2010 when CutYourSim started the Factory unlocking for $200 almost through someone working higher up illegally whitelisting the IMEI numbers, those iPhone's never got re-locked.