After patching some test ESX hosts with ESX 3.5 Update 4, the problem with the VMware tools being shown as "Not running" after a VCB backup operation seems to have been solved. This has cured some backup woes at least.

I will now run ESX 3.5 Update 4 in a test cluster (with virtual machines that will be backed up with VCB) for a few of weeks before updating production ESX hosts to Update 4.