>>40>Every time creature takes a step, it recalculates the path to ensure its validI will admit I haven't played since 0.40.8, but I'm pretty sure this isn't true. In my experience, a creature will only notice an obstruction when it reaches it.
What does affect pathfinding is how many tiles the algorithm needs to consider before arriving at the destination. Pic related is how A* works, one very popular algorithm (relatively easily extended to 3D and exotic movement rulesets).
Actual distance obviously is one consideration (which is why on larger maps, the pathfinding may take more time).
Symmetric branching paths probably increase the time, as each of the branches needs to be considered even though the two paths are equivalent.
A tree structure is probably rather efficient, since the wrong branch will probably be in a direction away from the destination and thus not be extensively considered.
If the correct path is a branch that loops around a large area from within which the destionation is not accessible, the pathfinding might consider most, if not all tiles within the dining hall before backtracking and considering the small side tunnel.
Building a huge sphere is optimal for distance (I think. A cube might be better after considering the limitations of dorf geometry), but you should be careful connecting rooms and digging shortcuts up or down, since there's a risk a "tendril" of the pathfinding algorithm will stick down there when it shouldn't.
But yeah, the main thing is the number of creatures. Limit your population to a value you find bearable.