Techniques are described for providing virtual networking functionality for managed computer networks. In some situations, a user may configure or otherwise specify one or more virtual local area networks (“VLANs”) for a managed computer network being provided for the user, such as with each VLAN including multiple computing nodes of the managed computer network. Networking functionality corresponding to the specified VLAN(s) may then be provided in various manners, such as if the managed computer network itself is a distinct virtual computer network overlaid on one or more other computer networks, and communications between computing nodes of the managed virtual computer network are handled in accordance with the specified VLAN(s) of the managed virtual computer network by emulating functionality that would be provided by networking devices of the managed virtual computer network if they were physically present and configured to support the specified VLAN(s).