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.
Do you have any idea how profoundly ungainly this is? First of all, you're talking about a set of keys that is over a thousand times that of all the SSL key pairs in existence.
Then...who issues the keys, and how do you secure them? (Exhibit 1: problems with forged certs from insecure CAs)
How do you revoke that authority if necessary? (Exhibit 2: problems discovered by the military as they contemplated DNS servers running DNSSEC in combat zones where they could be overrun and captured).
How do you know which kill switch cert goes with which device? (Exhibit 3: AMI meter deployment problems where the meters were mis-deployed, causing incorrect billing attribution)
Finally: How much will this cost...to stand up an unprecedentedly large PKI infrastructure, the governance around who would own/manage it, to license the tech (patents abound with TPM) and to incorporate it.
Look into the NISTIR 7628 guidance from NIST and you will get a brief glimpse into the horrors of incorporating PKI into a group of devices that numbers tens of millions. It's not simple. For further info, look up the comments by Annabelle Lee on the topic.