I had a customer that had some backup jobs that failed with this error "Task failed, Error: PhysicalHost with id 'xxxx…' was not found", and it looks likethis.
We found the host that this machine was running on, and this host was reinstalled.
After some searching i found that there was 2 record in the Veeam database table for this server with the following SQL query:
use VeeamBackup Select * from dbo.hosts where name='<FQDN hostname>'
So I disabled all jobs (waited for the jobs to be stopped) and then stopped the "Veeam Backup Service" service, and made a backup of the database.
Afterwards I deleted both records from the table, with this command:
use VeeamBackup Delete from dbo.hosts where name='<FQDN hostname>'
Check that the records was deleted, and started the service again "Veeam Backup Service", after the service the record was recreated again, and now there was only one record. ran an scan on the vCenter and enabled all the jobs again. And now the backup job was running without any problem.
NOTE: If you see this, Veeam support can help you. Using this solution without engaging with with Veeam Support is at your own risk