I am having a very similar issue.
Veeam 9.5 latest update
I added a new Backup repository, which went fine. When I tried adding the proxy of the same name I get "VMware backup proxy already exists on server XYZ". I have only added the repo.
I removed the repo, uninstalled all the Veeam programs that get installed on the repo when adding. Rebooted the repo, reboot Veeam and then re-added the repo, then I tried to ad the proxy. Same error.
I have done this many times with other repo's and proxies (we have 13 of them) and never had this issue.
Any help is appreciated