A first message of a first type and having a first destination address is received in a provider network. The first destination address is associated with a virtual network address of the provider network and an address of a first device in an extension of the provider network, the extension of the provider network in communication with the provider network via at least a third-party network. A message state data store is updated based on at least a portion of the first message. A first payload of the first message is sent to the first device a first secure tunnel through the third-party network.