The Z-Wave network, while being a mesh network, is not a dynamic mesh. Nodes follow a precomputed path from themselves to the controller (with backup paths -- it's based on a node having a predefined list of adjacencies). You need to regularly poll each node in the system and determine it's optimal path from controller->node and node->controller and redefine it's adjacency list.

This process is entirely automated but does take some time. It's absolutely critical to do this when adding a new device (both for the new device, as well as the overall network) but I found that just doing it regularly works great. I have all my networks configured to do this at 4AM daily since the network is unusable for the few minutes it takes.