Your Veeam backups can be working fine and then suddenly start to fail after upgrading ESXi or vSphere. This is because Veeam stores references to ESXi hosts in its SQL database and it thinks that the upgraded VMware ESXi hosts are new servers. It fails to update the Hosts table and gets confused by duplicate records, causing the backup to fail.
To fix this, open the VeeamBackup database (by default your Veeam database will be a SQL instance called Veeam, residing on your Veeam backup server). Edit the Hosts table, removing duplicate IP addresses with older versions of ESXi depicted by the Info column.
This is a known bug in Veeam Backup and Replication 6, hopefully there will be a patch to fix this in future.
Addendum: You may find that you get an error saying something tot he effect of Host not found followed by a GUID. This will stop you from adding and removing VMs to backups, setting up exclusions and will probably give you the host not found error when you start Veeam. To fix this one, remove the GUID from the Folder_Host table in the VeeamBackup database.