Techniques are described for providing managed virtual computer networks that have a configured logical network topology with virtual networking devices, such as by a network-accessible configurable network service, with corresponding networking functionality provided for communications between multiple computing nodes of the virtual computer network by emulating functionality that would be provided by the virtual networking devices if they were physically present. In some situations, the networking functionality provided for a managed computer network of a client includes receiving routing communications directed to the virtual networking devices and using included routing information to update the configuration of the managed computer network, such as to allow at least some computing nodes of a managed computer network to dynamically signal particular types of uses of one or more indicated target network addresses and/or to dynamically signal use of particular external public network addresses based on such routing information.