You are correct that cryptography is not a cure-all to all problems, however, your post goes irrevocably wrong immediately after that. HSM and TPM chips are quite secure and well established. The example problems you suggest are in no way relevant to the conversation at hand since they deal with an entirely different use case of security. As dmbasso was kind enough to point out, I am referring to the use of asymmetric cryptography to allow secure validation of a private key being held remotely. Such cryptography is used all the time (any time you use an HTTPS page) to prove the exact same thing.
The device merely has to hold the a public key for which the legitimate owner (or the vendor) has the private key. If the device is stolen and locked, it is trivial for an HSM to prevent unlock without the private key. It may be possible to circumvent the kill switch by yanking the HSM, but such an operation would likely exceed the black market cost of the majority of phones as it involves painstaking processes such as removing the silicon one layer at a time with a very carefully applied acid bath, and even then, the write once public key address space would be just as secure as any write once kill switch flag that could be implemented.
To prevent re-activation of the kill switch itself (rather than the recovery mechanism) the switch could be tied in hardware to a similar challenge response against a private key held in the device's HSM. To "kill" the device, this private key would be wiped, preventing the device from starting. To re-initialize it, the private device key would be restored by looking for a key signed by the owner's private key.
This is a simple to implement and highly secure system that would be cost prohibitive to work around and also could use available, near off the shelf components to implement.