Is the destination backup datastore present to every host in your cluster?
Yes it is. I even umounted and remounted the datastore on all hosts. It is mounted via NFS from a CentOS 5.8 host.
FYI, all VMs are backing up to the same datastore which makes it even more confusing why most will back up but certain ones won't. It's always the same VMs which don't back up.
With all the issues going on I had forgotten that when I upgraded my hosts to ESXi 5.1, I had also updated vMA from 220.127.116.11 to 18.104.22.168. When I recalled that, I restored a backup of vMA 22.214.171.124 which resolved this issue.