I switched to Cingular from Verizon about a year ago because Cingular has GSM phones, and I want to use my phone when travelling to Europe. I got Cingular 3125 (a.k.a. HTC Star Trek, a.k.a. QTEK 8500), based on Windows SmartPhone WM5. The phone, of course, was locked by Cingular. Now the time came for me to take the phone abroad, and knowing that there are two ways of unlocking the phone: through the provider, or using 3rd party tools/services, I started with less risky - called Cingular.
I called Cingular (the new AT&T) help line and told the tech support lady that I was travelling to Europe and would like to have my phone unlocked. Without even asking me what country I am travelling to, she said that they will not unlock my phone and instead I would have to pay for their international roaming package.
Then I tried cellunlocks.com - one of the many services that claim to unlock the phone remotely. I paid $6.99, followed the instructions - only to receive the email stating that unlocking my phone was not possible, with no details about why, and that the full refund will be posted within 10 days. Eight days later there is still no refund, so you may want to stay away from this "service". UPDATE: Refund was finally posted two weeks after they stated they can't unlock the phone.
Then I called Cingular again, and this time I told the rep that I am travelling to Ukraine, that I will be using SIM card provided to me there, and that I would like to have my phone unlocked. This rep seemed more attentive. First, he made sure that my phone will work on Ukrainian networks. Then he said that they will unlock the phone. He made me pull IMEI ID and placed an unlock request with Cingular. Within hours I received the call from Cingular with the unlock code and unlock instructions - all I needed now is a SIM card from a foreign GSM service provider, because phone prompts for unlock code only when "non-naive" SIM card is inserted. Luckily, my relative visiting us here, had her SIM card with her. I popped it in, entered unlocked code and that was it.
I suspect that I was successful in my second attempt to unlock the phone through Cingular because they probably don't have roaming agreement with Ukrainian providers.
The bottom line is: If you want to have your provider unlock your GSM phone, tell them you are travelling to a country that does not have roaming agreement with your provider.