Hi EvilSOB,
I see what you're saying. I too believe that Zinc isn't for you. If I was working on a project like that, I'd use some kind of tile-grid system, so each time you dynamically create chunks of terrain, you set some sort of flag to indicate if that chunk of terrain is passable or not (has a building on it). Then, use A* to dynamically find routes around your terrain.
Even if you could add waypoints at run-time in Zinc, it would be a bad idea to actually keep the graph generator running while the actual game runs since graph creation is an intensive process using many c_traces and not intended for run-time use. But if you use tiles with an obstacle flag that you can turn on and off, you won't need to be doing any c_tracing.
I'll be interested to know how you do tackle this problem. Let me know if I can be of any help. Intense Pathfinding 2 has been discontinued, but I could send you the lite-c A* code from it, if you'd like to use it in your tile-based search space, or whatever you decide to do.
Cheers,
Aris