Well, at a certain point, we are optimizing for several different priorities at once - we need to optimize the amount of time it takes to build the graph, optimize the time it takes to use the graph, optimize the memory usage of the graph, and optimize the functionality of the graph.
At some point, we can generally just say "screw it", and go with a sub-optimal graph that takes more time to path through than a purely optimal graph, just because we wanted to make the graph itself faster, and just took a reasonable guess.
I also think that having some sort of end-of-the-season stop-and-sweep-up-any-mess-in-the-graph phase to make sure that we can try to put together some optimal paths might be a nice way of getting some balance in the performance, so that long-unchanged paths can be assured of optimization would be a decent way to make sure some heavily used paths are optimized without having to jump through a more complex optimization process very frequently.
Something I'm not entirely sure we should overlook too soon, however, is ways to make some of these node non-rectangular. It might mean having to save some extra data into memory to ensure best paths or else involve some fairly quick A* work inside the node, but let me give an example...
Someone wants to build a really fancy hallway leading up to the dining room, with plenty of statues to impress visitors of the greatness of dwarven society...
(tricky) Case A:
##################
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
.................+
Ω...Ω...Ω...Ω...Ω#
.................+
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
##################
(sadistic) Case B:
##################
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
......Ω...Ω......+
Ω...Ω...Ω...Ω...Ω#
......Ω...Ω......+
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
##################
Now, in the case A, you can do a psuedo-optimization by just drawing some nodes horizontally, one tile wide, directly past the doors. You wouldn't be able to make it a wide hallway, but you could make the game recognize some hallways, at least. I'm not sure how well traffic dodging will work in this situation, however.
This requires a case of the game being able to actually make an optimal decision on how to cut up these nodes, however, in order to get optimal results.
The case B, however, will inherently screw any attempt at making an orderly straight line through the hallway over. You're going to have to make the pathfinding program find a way to dodge occasional obstacles in otherwise straight hallways.
Now, what I'm wondering if we could try to do is make slightly more permissive definitions of nodes than just drawing rectangles, and then going ahead and either recording an optimal path through the hallway (costs memory), or else just letting a "local A*" type of pathfinding take place (costs more processor power at the time pathfinding takes place), but at the same time, making a much simpler node graph (saving some memory and time spent searching paths through the nodes), but also taking some more complex node-generation techniques (taking more processor time when building the graph itself).
Hallway case A, for example, could have one node taking up all three middle rows of tiles (not including the alcoves), and record that there are some obstacles in some of those middle tiles, and the whole hallway would just be a single node, and dwarves could path up and down diagonally through that hallway if they so chose, weaving in and out of those statues if there was an obstruction like a traffic congestion down by one of the statues, and they had to go around to save time.
Hallway case A might even fill to include the whole darn hallway, alcoves and all, and just have plenty of obstructions out along the sides as well as in the middle to avoid.
Either way, you could have some sort of very basic A* pathfinding that would work very, very well, or else have a pre-saved optimal path from one exit of the hallway to another that ties up memory.
Hallway case B might have the entire hallway stored as a single node, once again, with an optimal path to and from exits based upon the sort of highway system, to avoid traffic collisions:
("<" means the "going left" path and ">" means the "going right" path)
##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################