Hello Andrew Shepherd,
Below are the few troubleshooting steps which can help you to resolve the issue.
Firstly, the issue might happen if any file or folder corrupt occurred or does not have the updated or latest credentials with the recovery service. In this scenario, you can either create a new vault credentials or create a new vault to avoid conflicts.
To make vault credentials work as expected, make sure that the MARS Agent is up to date, and the older versions may lead to validation errors as shown in the below snap. Try to download the vault credentials into a specific directory and use that to proceed further for avoiding issues. You can download by going to "properties" under vault.
And also check the certificates existed on the server by visiting control panel and remove the certificates which are not in use to avoid confusion when the reinstallation registration process runs again.
In the Azure Portal, under the backup vault, verify the Backup Management Servers and remove any registrations from previous failed installs existed.
Check if there are any network restrictions or firewall blocking you to validate and proceed with the vault credentials. Refer MSDoc for more relevant information on the issue.
Hope this helps.
If the answer is helpful, please click Accept Answer and kindly upvote it. If you have any further questions about this answer, please click Comment.