I wonder if that message that the phone is unlocked only appears once? Say you restore a second time, would the message appear again? Also, does it have to be a restore from itunes? I am now backed up completely on iCloud, how's the process on that? Or do I have to backup to itunes/pc/mac for the mean time?
I can confirm that the message will appear as many times as you restore it. The iPhone itself does not produce a message if you do not go through the iTunes process but if it's unlocked it should accept the carrier's SIM.