An example method for routing a message in a dynamic service mesh includes receiving at a mesh point a first message from a sender service and determining, based on a routing table, whether the mesh point has previously received a second message from the sender service. When the mesh point is determined to not have received the second message from the sender service, the first message is routed to a target service in the dynamic service mesh. The method includes receiving an indication of whether the first message has been accepted by the target service and updating the routing table based on the indication. When the indication indicates that the first message has been rejected by the target service, the first message is routed from the mesh point to a second target service.