HA works completely indipendant of vCenter. Hosts really only need access to vCenter for configuring HA, but not for the handling of restarts.
There seems to be a fair few events of "Virtual machine was restarted on host-esx03.fqdn.int since host-esx01.fqdn.int failed" followed immediately with "Failover unsuccessful for this virtual machine" even though the VM *was* moved from esx01 to esx03 but not powered on
I suppose you use FC storage or your NFS/iSCSI network was not affected from these networking issues?
Then I can think of the following scenario as to what might have happened: The hosts were partitioned (not isolated or could still reach their default gateway) at first and tried to restart VMs of the unreachable hosts. However, they couldn't restart the VMs because the VMFS file lock was still active as they haven't been shutdowned. Later the issue expanded and the hosts actually all got isolated, applying the isolation policy of shutting down VMs. This could have happened through a switch reboot for example, causing (non-rapid) spanning tree to block all ports for a while until the tree is built. You may want to set the HA setting das.failuredetectiontime to a larger value like 60 seconds (default 15) to guard against this.
To really tell what was going on we'd need detailed aam/hostd/vmkernel logs and descriptions of what precisely went wrong on the networking side.
Anyways, I generally recommend using the leave powered on isolation policy to avoid such issues. VMFS file locking will do the job in 4.x and in vSphere5, you have datastore heartbeating adding even more resiliency.
Check the awesome HA deepdive and books by Duncan and Frank:
http://www.yellow-bricks.com/vmware-high-availability-deepdiv/#HA-41