Ok, I finally got a AT&T SIM to make sure the phone is unlocked. Once I used the AT&T card, I was again challenged to provide unlock password. Previously, I entered the unlock code using: #7465625*638*, but it looks like this was not respected, and/or did not stick.
So, I entered the unlock code again, then I saw 'requesting unlock request' message. Then I got the 'unlock successful' message.
To verify the unlock status: *#7465625#; however still nothing is listed. Oh, well...
So after all I got the unlock to work.
BTW: guys who provided the unlock code were: freeunlocks.com; Yes, you have to sign up for some crappy service, which you can cancel later.... but the price is right! The guys provide very good support as well.