My theory is that if your 4S was purchased from AT&T, they have more accurate records whether the contract was fulfilled or not, so they are more likely to deny the request.
However, if your 4S was originally purchased at the Apple Store or replaced under warranty at the Genius Bar, AT&T may not have enough information to deny your unlock request.
I just called today to get my dad's 4S unlocked. His contract just ended yesterday, but my sister purchased the 4S for him using her upgrade at an Apple Store a few weeks after they were released. I was expecting them to deny my request, since the 4S is technically still under contract, but after waiting on hold while they checked the IMEI number, they eventually told me that it's eligible and processed the unlock.
If the upgrade was purchased at an AT&T store, I bet they would have denied my request even though his contract had ended already, because they would have been able to see that the 4S was purchased under contract.