VC in which the native key provider was enabled got deleted and couldn’t recover it from the backup. Unfortunately, there is no other backup for the primary key.

 The only option to recover is to clone VMs to remove the encryption and then cutting production over from the current live VMs to the clones. If this does not prove successful, the VMs will need to be rebuilt. 

We need to make sure to backup the VC and protect the primary key in a safe place.