[TrueDuality]

It is largely impossible to fully prove. CAs are supposed to keep detailed records of any issuing keys and what was called for was specifically "witnessed Key Destruction Reports" which involves third party independent confirmation of destruction of documented keys.

In the event that a key with a Key Destruction Report shows up again, the responsible party for that key will have shown unacceptable negligence and will potentially be subject to the exclusion of their keys as a valid certificate signer.

A lot of these companies core businesses rely on remaining in a position to sign certificates so it is in their best interest to protect that privilege by following the documentation requirements, and properly destroy their keys. It's effectively a pretty good stick.