In my opinion a labyrinth would be counter productive It would take you more and more cpu resources to find a path. In order for it to work you'll have to trap someone in it somehow (probably a presure plate) and tell your dwarves to avoid it using traffic zones.
If there are optional routes, dwarves will reroute if they encounter other dwarves, even if the new path is longer. Even if it's like 10x times longer. They don't crawl if they don't need too, which is sometimes stupid.
This explains a few things in terms of path finding and FPS behavior.
For a while I tried to figure it out if pathfinding is the real FPS killer. Devek has made a valid claim that pathfinding can't be it, because it doesn't happen that often. Still if things are as you claim it explains the fps gradually dropping rather than fluctuating .
If the dwarves are in an enclosed space they would each find a path for themselves and the chances they''ll collide with someone grows . At many intervals a group of dwarves may find they can't step into a path because another creature is there. If they recalculate the path they may get a failure due to the blocking creature. a path failiure means A* will go through all the accessible nodes. This may cause heavy backtracking inwards .
This is a major trouble if a few dwarves are trapped between two groups . They may oscillate back and forth. This can also be worsened if a dwarf is searching for an accessible item. if it gives up as soon as the item is inaccessible it looks for another one. If he's trapped he may try to find a path to each and every valid item in the port (I'm sure there is some sanity check). if he's not traped he can be fooled by the heuristic to try and reach items bellow or above him that may look closer but are really far away. What you get is an 8 way intersection where everyone has a green light and right of way.