Embodiments are directed to stateless communication using a stateful protocol. One or more NTMAs may establish a connection with a client computer based on data exchanged with a the client computer using the stateful protocol. The exchanged data may include validation information provided by the one or more NTMAs. The exchanged data and other information associated with the connection may be discarded from one or more memories of the one or more NTMAs. A network packet communicated over the network using the stateful protocol may be obtained. Verification information and candidate validation information may be generated based on one or more characteristics of the network packet. The network packet may be validated based on a comparison of the verification information and the candidate validation information. A reply that adheres to the stateful protocol may be provided to the client computer based on the validated network packet.