Provisioning of desktops fails after adding new host to the cluster

After adding a new ESX host to the environment provisioning of new VMs fails. We can see messages like these in View Manager event log:

Desktop Composer VcFault: see event log for full error - Host has been disconnected in VirtualCenter - <fault xsi:type="HostNotConnected" xmlns="urn:internalvim25" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" />
Pool cn=803e9410-be45-45b1-914d-63052824059b,ou=virtualcenter,ou=properties,dc=vdi,dc=vmware,dc=int::Unable to create new VM - Desktop Composer VcFault: see event log for full error
VirtualCenter control for https://xxx-srv008.xxyyzz.com:443/sdk is suspending operations - VM operation failedMessage:  VC_DISABLED:VC:cn=803e9410-be45-45b1-914d-63052824059b,ou=virtualcenter,ou=properties,dc=vdi,dc=vmware,dc=int;REASON:VM operation failed;
Desktop Composer Error:VMware.Sim.Fault.VcDatastoreInaccessibleFault; Error Type:com.vmware.SviService.VcDatastoreInaccessibleFault;Error FaultActor:null; Error code:{http://schemas.xmlsoap.org/soap/envelope/}Client; Error details:[Lorg.w3c.dom.Element;@980c0a
Desktop Composer VcFault:VMware.Sim.Fault.VcDatastoreInaccessibleFault
Pool cn=803e9410-be45-45b1-914d-63052824059b,ou=virtualcenter,ou=properties,dc=vdi,dc=vmware,dc=int::Unable to create new VM - Desktop Composer VcFault:VMware.Sim.Fault.VcDatastoreInaccessibleFault

This problem occurs if the new host is unable to access all the datastores that is being used by VMware View.

Note that this also happens even if this new host is in maintenance mode. The solution is to move the host out of the cluster until it can see all the needed datastores.