You don't need PKI around this though. You just need key pairs, not key storage, so PKI isn't a problem. You have a few private keys for the manufacturer to be able to verify they are signing off, this is easier than existing SSL concerns. Then you have the public key embedded in each device for which the consumer has the private key on the separate dongle. This isn't inherently all that different from the way electronic car keys work when they are actually using a secure exchange.
You don't need a trust delegation system since the devices are assigned the keys to trust at creation and you don't have a large number of keys to secure since the public key information doesn't have to be secure for each phone and only has to be accessible to customer service at the manufacturer.
You bring up a valid point about revocation concerns for the manufacturer's portion of the validation, but the worst case scenario of a compromise is that attackers could lock phones once and then the phones would be unlocked and the lock disabled to avoid future problems. If the manufacturer themselves is compromised, they the revocation list could be faked too anyway since it would effectively be a compromised CA.
I would suggest that to have the phone locked down, the customer would have to supply the private key associated with their device or answer some local challenge. The USB key that came with their device would provide the public key and device ID information needed.
Cost shouldn't be substantially more than the cost of the USB dongles and TPM hardware. It would still be an additional cost, but probably not much more than a few dollars per device. Note that I'm not even saying I agree with it being a legal requirement either, I'm just pointing out that it is not as complicated or risky as it might initially seem.