I am experiencing something very similar and boy is it annoying, here is what I have found.
The VCSA performs a dns query on the domain, such as domain.local this is completely expected but.
From a windows PC connected to the domain run nslookup domain.local
In our domain this lists all of the domain controllers of which there are 16.
so running the command looks like this,
nslookup domain.local
server: DNS.domain.local
address: 192.168.1.1
name: domain.local
address: 192.168.1.1
192.168.2.1
192.168.3.1
...
Now from the VCSA command line pinging domain.local, what you will see is that the DNS will return a round robin of the IP addresses.
First time running ping 192.168.1.1
Second time running ping 192.168.2.1
Third time running ping 192.168.3.1
....
In our case of the IP addresses returned only 2 DC's in the list could actually be contacted by the vlan the VCSA is on.
Believe it or not it would eventually connect to the domain as long as you kept trying as it would round robin though all the servers until it could actually connect, this however is not very practical.
try the tests above and let me know if you see anything similar