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 188.8.131.52 to 184.108.40.206. When I recalled that, I restored a backup of vMA 220.127.116.11 which resolved this issue.