The phone doesn't so much "present itself differently", it's just that Apple keeps a list of IMEI numbers and their lock states.
So far as I know they are all sold identically, apart from the serial-number type bits (BT/WIFI MAC, serial no, IMEI, probably a few other things). This makes the most sense, too, because those numbers have to be unique for each iPhone anyway and this can thus be made into a step in the production process (hell-- two of them are laser-engraved into the SIM tray). The linking of an IMEI to a carrier (with or without lock) can then be done at a later time. This allows their inventory to be treated identically for as long as possible, and thus be maximally flexible. They haven't just created a batch of 100 AT&T iPhones, or 100 Vodafone iPhones, or 100 factory-unlocked iPhones. They've just created a batch of iPhones. So if AT&T suddenly needs 150 iPhones but Vodafone only requires 50, they aren't in trouble.
Obviously I don't work for Apple and the only ones who can be sure of this are people who do, but that's what I've gathered off the interwebs.
Now, if a carrier-unlocked iPhone always has iTunes tell you 'yay!' on restore (which btw is new to me), that means that indeed the originally locked state is recorded somewhere. And since iTunes has to get this info from Apple's servers, my money is on it being there.