I assume maybe you found and followed this info? I have some info on my results here: Reset zwave routes - #11 by jtp10181
Usually the automatic routing is pretty good though even if you take a device out of the picture. I am still suspecting a spammy devices is what is causing the issues especially since it has persisted for 3 weeks.
