A method of operating a web service atomic transaction (WS-AT) system includes: receiving, at a processor of an extensible markup language (XML) gateway, a first message from a communicatively coupled client, and inserting a WS-AT Transaction Identifier (ID) from a Simple Object Access Protocol (SOAP) header into a hypertext transfer protocol (HTTP) header of the first message to generate a first modified message. The method also includes: receiving, at a processor of a network device communicatively coupled to the XML gateway, the first modified message from the XML gateway, determining that the WS-AT Transaction ID is not yet associated with a service provider in a routing table, and in response, sending the first modified message to a particular service provider and associating the WS-AT Transaction ID with the particular service provider in the routing table such that future messages from the client can be routed to the particular service provider.