1. A computer-implemented method comprising: providing, by one or more computing systems of a configurable network service, a virtual computer network having multiple computing nodes for use by a customer of the configurable network service, the providing including assigning one of a plurality of virtual network addresses for the virtual computer network to represent a Lightweight Directory Access Protocol (“LDAP”) service that is made available by the configurable network service externally to the virtual computer network; and initiating, by the one or more computing systems and for a communication that is sent by one of the multiple computing nodes to the assigned virtual network address for the LDAP service, providing functionality of the LDAP service to the virtual computer network by encoding the communication in a manner specific to a substrate network on which the virtual computer network is overlaid, and by forwarding the encoded communication over the substrate network to at least one LDAP computer server of the LDAP service that is external to the virtual computer network.