This is still true for 5.0 to 5.5.1 ESXi Upgrades. Once you find this thread you will be fine, the solution still works
Due to Upgrade of ESXi hosts from 5.0 to 5.5.1, Veeam lost its relationships to hosts.
Task failed Error: Host with uuid '34333336-3430-5541-4431-32393033544b' was not found
(additional complaints about licencing seem spurious so may go away when the hosts issue is corrected).
Tried re-adding the guest vm in a job.. fails
Tried rescanning the backup infrastructure .. the rescan worked but the backups fail with same errors.
which seems to be the first two things 'everybody else' tried.vmware-vsphere-f24/vsphere-hosts-updates-uuid-error-t5945-15.html
The suggestion is to revoke the licencing of the hosts, (top-left dropdown, help, licencing, button:'licenced hosts', then rescan, and re-try a failed job.
* Manual retry of failed job, succeeds.
* Automatic retry (lucky coincidence with timing), succeeds.
* Standard run of next job with start time after time licences were revoked, succeeds.
Watching the licencing, each host is re-licenced as it is referenced in a backup job (depending on where VMs are currently residing)
Veeam is the best recovery solution I've ever had, I admit to skipping a heartbeat when the backup showed red but it's all good again now.