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