Found out the hard way: don't use underscores in hostnames. It's not allowed by DNS, and it breaks things. In this case: joining vCenter Server Appliance (VCSA) in an Active Directory doesn't work if the hostname of the appliance contains an underscore (_). It also doesn't work if the hostname is "localhost".
If your appliance uses DHCP, the appliance gets its hostname through reverse DNS. So in that case, it _is_ a freaking DNS problem.