Hello Alex Toniati
That is absolutely correct. You need to move the VM to another RG(Can be a new or any other existing RG) in order for it to change VMs resource ID. The reason for this act is to make the VM instance ID as new in the azure service side in order for it to get registered under backup service once again as a new VM. As long as the existing resource ID is same it won't register with the backup service.
After this I bet you know what to do next..
Good luck!
<Please accept answer and upvote if the above information is helpful for the benefit of the community.>