Hi Paul,
Are you saying the VM's disk(s) were encrypted using Customer Managed Key and you deleted the key vault that contains the key? Please correct me if that is not the case.
What you can do is recover the deleted key vault by navigating to key vaults -- manage deleted vaults. Once you recovered the vault you can navigate to the VM's disks -- Encryption blade, switch to Platform Managed Key, Save, then test that you can start the VM.
Note that if you deleted the key before deleting the vault you will need to recover the vault first, next recover the deleted key, then make changes to disk encryption.
Please click Accept Answer if the above was useful.
Thanks.
-TP