In a distributed architecture it is very difficult to avoid the possibility you mention even with a strongly consistent store at the center of your service disc

In a distributed architecture it is very difficult to avoid the possibility you mention even with a strongly consistent store at the center of your service discovery mechanism. The consistency the store provides doesn't necessarily extend to the operational state of your system. For example, your zookeeper nodes may all be consistent with each other, but given that a server can fail at anytime, that information while consistent may still be stale. Likewise, if a client is caching connections outside of zookeeper's consensus mechanism, then these connections will also become stale in the face of changes. Given these possibilities, there is always the potential for traffic to be dropped on the floor regardless of how consistent your store is, so ultimately what matters is how to minimize the probability of this occurring and whether your system can cope when it does.