Even factory unlocked iPhones need to be unlocked via iTunes. By default all iPhones are locked and when they are restored, iTunes checks with Apple to see if that particular iPhone can be unlocked. Apple can lock or relock all iPhones and iPads simply by removing that device from the unlock database.
Nobody has disagreed with that*, but the "Congratulations, your iPhone is unlocked" message doesn't normally appear if you bought your phone directly from Apple "factory unlocked".
My iPhone 4 shows that message when I restore in iTunes because I bought it from my old carrier and they unlocked it for me (for free).
*Except I will now! How can all iPhones be locked by default? Which carrier would they be locked to?
The real answer is that an iPhone is not locked to any carrier until it is activated. Apple sends an
WildcardTicket to the device at the time of activation which tells the device which carrier(s) it is locked to and whether a country lock is in effect (as is the case with Verizon/Sprint unlocks).