A mechanism to facilitate a private network (VPN)-as-a-service, preferably within the context of an overlay IP routing mechanism implemented within an overlay network. A network-as-a-service customer operates endpoints that are desired to be connected to one another securely and privately using the overlay IP (OIP) routing mechanism. The overlay provides delivery of packets end-to-end between overlay network appliances positioned at the endpoints. During such delivery, the appliances are configured such that the data portion of each packet has a distinct encryption context from the encryption context of the TCP/IP portion of the packet. By establishing and maintaining these distinct encryption contexts, the overlay network can decrypt and access the TCP/IP flow. This enables the overlay network provider to apply one or more TCP optimizations. At the same time, the separate encryption contexts ensure the data portion of each packet is never available in the clear at any point during transport.