A few thoughts I've had on the issue:
First, making something multithreaded doesn't actually make it more efficient, to my knowledge - it just means that if you have multiple processors, they can each focus on a part of the task, rather than just handing it to one processor while the rest do unimportant background stuff. This means making something multithreaded will likely be an amazing speed boost for someone who has multiple processors - for someone who doesn't, not only will it not have any improvement, but it's possible that it'd go even slower from the additional system overhead.
I happen to be one of those people who doesn't have multiple processors, so I hope you can all understand as I try to cunningly switch this topic in the direction of more efficient pathfinding, rather than or perhaps in addition to multithreaded pathfinding.
That said, I'm not too experienced on matters of pathfinding. I think I understand the A* model of pathfinding enough to talk about it, but in truth my ideas are a little more generic.
One issue I see with A* pathfinding is that while it's amazing to find the path for situations where you really don't know, beforehand, where you'll start and where you'll end, in DF, you tend to figure that most dwarves who go through a hallway (particularly a 1-width hallway) will go a very specific route; straight through. With just using A* pathfinding over and over again, you're essentially calculating commonly-used routes over and over again.
So I was thinking... why not have some method to remember those routes, or possibly precalculate potential routes. In games where the map doesn't change, you could easily precalculate all sorts of things, but unfortunately, at least in fortress mode, DF's map does change (unless you're playing elves or something, but who would want to play those?)
Therefore, that splinters my idea around a bit. First, I thought... why not have the routes slowly come into existance, through some almost evolution-based method, coming into existance randomly based on moving units, changing/branching off into clone routes/etc., and dying off when other routes are used in favor of them.
For this method, it wouldn't take very long to give some control of this feature to the player - both in general settings (since this is a sort of diversion from CPU power to memory, this would allow people with lots of memory to just say "eh, screw it, let's make thousands of routes", or something), and in actually making the routes. This could even be used as traffic control, by allowing routes having customizable costs as well, as far as the pathfinder is concerned (the end result would function like the current traffic costs, except applied to a sort of pre-created path rather than the tiles that path is made up from.)
Another idea, one that I don't see any easy way to do at all, would be to predetermine these so-called routes based on some algorithm, and as the map changes, to rewrite the routes. I'm sure others have ideas that look like this one, only better in every way.
For those who have no idea what I just said, but have some understanding of A* pathfinding, let's take an example. # are walls, . are floors, 1 and 3 are beginnings of the route, 2 and 4 are the respective route ends, @ is a dwarf, and D is his destination.
#..#####
#..#####
#.23..4D
#..#####
#.1#####
#@.#####
In this case, the calculation time saved isn't that much (about three iterations, probably), but, depending on the exact values used, an A* method would likely take the routes from 1 to 2, then 3 to 4, then to D anyway. Using routes, 1 would effectively also lead to 2 (in addition to all the adjacent tiles), and likewise 3 would lead to 4. If going from 1 to 2 seems the most viable, it'll apply the pre-constructed path, as if it had calculated it itself, and continue from there.
I'm unsure of any flaws in this method, having only just gotten the idea last night and not having managed to test it in practice yet, so if there are any obvious ones, or if it's a fairly old trick that's long had its guts removed and has long been considered obsolete, then please say something. I'm really uneducated in this crazy pathfinding business; all I know is that, assuming DF's using standard A* pathfinding (or something comparatively like it), there're probably thousands of cases where it's recalculating the same thing over and over.
One final thought, unrelated to all this, is... who says there needs to only be one path finding method? There could be more, if, for example, strictly land-based pathfinding methods can be made more efficient than a flyer's pathfinding method. Another thought is that perhaps less intelligent creatures could use less efficient pathfinding methods (that is, in time it takes to get from point A to point B, as opposed to CPU efficiency).
Brainless undead could use a simplistic "go in the best direction" method, and just sit there uselessly, or give up on that goal and find another place to try to go, when they run into a dead end, etc. It is characteristic of them, afterall!