So about three days later I finally receive so-called UNLOCK code:
T-Mobile Sim Unlock Request
Sim Unlock Reference: ********
IMEI: ***************Unlock Code: ********
Thank you for taking the time to contact T-Mobile. Below you will see the Instructions for unlocking your HTC device.
1. Insert the foreign SIM card
2. Power on the device and the display should read "Please input unlock code"
3. Enter the unlock code and the device should display "Phone is unlocked."
4. Allow the phone to scan the network (or manually click on the antenna icon to do this)It is very important that the instructions and SIM unlock code are entered correctly as listed. If you receive an error message while performing the instructions do not make any further attempts to unlock the handset. Please be aware that if an excessive amount of incorrect attempts are made, the phone will be permanently locked. You will need to verify the IMEI by pressing *#06# and contact Customer Care for support.
Thank You,
Sim Unlock Department
T-Mobile USA, Inc.
Now I still cannot unlock the phone, because I don't have foreign SIM card. Gotta find someone with AT&T or Verizon SIM card. Also, I recall having AT&T SIM card somewhere, the one I got with iPhone purchase, but cannot locate where it is.
So I guess there _will_ be part IV of this ordeal. 
Update: No part IV will be needed, I got a hold of AT&T SIM card and managed to unlock this phone in under few mintues! I took a quick video of it too, crappy quality though.