Is there a known way to unlock an iPhone 4S running the latest software and baseband? I have not been able to find a service that will unlock it via IMEI. The phone is out of contract with Movistar Venezuela and they won't unlock it.
If the ones of eBay don't work for you, try contacting chronic since he seems to unlock phones outside the US based on what I remembered from his twitter feed some time ago.