My dad recently passed 90 days of service. He called CS and was transferred to the International Department, who instantly gave him the International Unlock upon his request. He told me this morning, and I asked him if he's synced the phone yet. He said no. So I synced it for him, and sure enough, the majestic "Congratulations, your phone has been unlocked!" appeared in iTunes. I stuck an inactive AT&T micro-SIM inside, and got the Invalid SIM message. It said to contact the carrier. I wish the FCC would do something about this phone locking business. It decreases the resale value of the phone and creates fragmentation in the market.
Example of this:
A family friend of ours got a Verizon iPhone 4. They are with Sprint, and the phone's intended user had recently dropped her Rumor Touch in the toilet. They actually had no idea it was Verizon. When they received the phone, Sprint refused to activate it. Now they have a $250 paperweight. She uses it on WiFi though.