Techniques for ensuring that, in the context of network traffic load-balanced across a plurality of service devices connected to a network device, all of the bi-directional traffic between a given pair of hosts residing in different domains is sent to the same service device, where a “domain” is a group of one or more hosts/subnets that is reachable by a service device via an interface of that device. In one set of embodiments, these techniques can include (1) creating a load balancer group on the network device for each domain defined on the service devices, such that the load balancer group for a given domain D includes all of the service device interfaces mapped to D, (2) enabling symmetric hashing with respect to each load balancer group, and (3) synchronizing the hash tables of the load balancer groups such that a given hash bucket (across all hash tables) maps to an interface of a single service device.