backup – BMSUserErrorContainerIsAlreadyRegisteredWithAnotherVault – Server Error

I can not create a backup service for a virtual machine. I receive this error during the creation:

Error Code BMSUserErrorContainerIsAlreadyRegisteredWithAnotherVault
Error message The virtual machine is already registered  registration in another vault of recovery services
Recommended Action Please select another virtual machine for registration.

This is nonsense because there is no backup service on this specific virtual machine. I can not find anything on the portal that says it is registered with another backup service.

Ideas?