yeah, you got stuck in the infamous Carrier / Manufacturer trap...they just tell you to call each other and neither take any responsibility. Your best choice to get the phone unlocked is to either send it away to someone, find someone locally, or Unlock the phone yourself with a cheap T28 Unlock cable, and the Total Server software program. What's really nice is that you will be able to unbrand your S710a which will remove all the lame cingular customizations found throughout the phone.
Good Luck! and if you have any questions feel free to PM, or email me!
Sincerly,
--Corey