Hi , I m facing the same issue as https://vox.veritas.com/t5/NetBackup/Operation-Status-4239-Unable-to-find-the-virtual-machine/m-p/877041 with Vms,
Below are the steps followed as per your suggestion, but the backup failing.
rebooted the VC, re-add...