I used "unlockclient com" these guys/gals (whatever) use some software you download to your computer. I checked it via Avast! (sandbox) to make sure it was clean. You plug in your phone via the data cable and follow the instructions:
1. Download and install drivers if you haven't done it yet
2. Take out memory card and SIM card and turn your phone on
3. Go to Menu > Settings > Applications > Development
4. Switch on the option "USB Debugging"
5. Go to dialer, type *#7284# and select USB -> Modem
6. Go to dialer, type *#9090# and select  USB
7. Exit service menu and turn your phone off by pressing power button
8. Insert NOT accepted SIM card and turn the phone on
9. Wait for "Enter Network Lock Control Key" message
10. Connect phone to computer and wait until all drivers are installed (~1 min)
11. Unplug the usb cable and plug it back
12. Enter your paypal email or test the connection for free first
13. When you feel ready, Click "Unlock" button
The software detects the IMEI. I took the risk of losing $25 to some scam. Boy was I wrong... The software verifies that you have paid them via paypal then does something to the phone via the data cable. At the end you have to enter 00000000 and boom unlocked.
Rebooted in my T-Mobile card and works. Now I have to flash the modem.
My AT&T (I717) phone was already rooted and on 2.3.6.