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