I want to clarify something about CDMA. I'm not intimately familiar with it, but in my experience don't you call up the carriers to activate your device? Well, normally the device you purchased would already be in their system. What I don't understand is, why can't you call them up with the serial number of an unlocked iPhone for them to activate? They already support the model, you just bought it directly from the manufacturer.
Besides, both Sprint and Verizon have made commitments to open up their networks to compatible CDMA devices so I'm not quite sure where you're coming from. From what I understand of what you're saying, it seems like CDMA devices are permanently tied to their network.
Links:
Verizon
Sprint
Also, as far as unlocking is concerned, nothing is done through iTunes. The unlocked phones that are out right now are being unlocked at the Apple Stores' POS system. This much is apparent from the article itself when it mentions the device being sold "Off Contract."
http://9to5mac.com/2011/06/26/apple...unlocking-full-price-att-iphones-at-checkout/
The message is a result of a previously locked phone being added to Apple's whitelist of unlocked units. I purchased a completely unlocked iPhone 4 when they were first made available in the US and received no such message when I activated the phone. Europeans, on the other hand, get this message after they request for their phones to be unlocked.