So it has been several weeks since my Part 1 post on this topic. We are still struggling with all of our servers getting backed up using AVVI.
I enlisted the help of a co-worker and he wrote an excellent vb script that queries the domain for all the servers, and then goes and restarts the VMTools service on every box. We run this script from our backup server, and it works great. This centralizes the management of that task, and keeps us from having to mess with batch files on every server, and potentially forgetting to add the task, etc. on a new server. You can download the script if you like. Change the .txt extension to .vbs, and edit the service name at the top. Edit the mail server settings at the bottom if you wish to get an emailed report of the results.
I believe that this new process has helped, but we are still having issues getting backups from all the machines. We have found that occasionally the mgmt-vmware service needs to be restarted on the ESX hosts as vCenter has trouble getting the snapshot. I have not yet taken the time to figure out how to automate this, so it is a manual process at the moment.