I believe the phone phones home to Apple to verify its unlock status, and this is only known for the store unlocked ones.

Hence the 'Successfully unlocked' message when you restore an unlocked phone.