Techniques are described for managing communications for a managed virtual computer network overlaid on a distinct substrate computer network. The techniques may be used in situations in which a configurable network service provides managed virtual computer networks for clients and also provides one or more network-accessible services that are available to the managed virtual computer networks, with particular managed virtual computer networks being configured to provide local private access to at least one of the provided network-accessible services, despite those provided network-accessible services being located externally to the particular managed virtual computer networks. In some situations, a Lightweight Directory Access Protocol (“LDAP”) network-accessible service is provided, and a logical endpoint for the LDAP service is created within a managed virtual computer network to enable the multiple computing nodes of the managed virtual computer network to communicate with one or more LDAP computer servers from the LDAP service.