Because it's apples activation server sending the lock, not the carrier's. Apple knows what lock state should apply for every IMEI. So when the phone is unactivated, you insert a sim, and the phone requests a an activation ticket from Apple. If the IMSI of the SIM matches one of the allowed entries, then the phone activates and let's you make calls. If the IMSI does not match anything in the allowed table, then the phone refuses to activate and gives you an invalid sim error
In other words, a brand new phone is completely locked, it is not valid for any carrier. It will not join a network until it gets an activation ticket that allows it, and Apple isn't going to issue an unlocked activation ticket unless the phone is provisioned for an unlocked ticket.