I think we must keep all channels open when it comes to the number of movement types we can deal with. We don't just have to cope with walkers, fliers, swimmers, jumpers, water walkers and lava-resistant creatures, but actually with a potentially infinite set. Pathing doesn't care whether a space is untraversable because it is impassable to the creature, or because it is passable but otherwise forbidden by the AI.
For example, we have the pets-and-doors issue, but in general this may be much more complex: different castes of creature may be allowed through different sets of doors (guards, workers, guests, nobles, the owner of a given room).
Then there's the issue of knowledge of spaces - an invader might not be allowed to path through spaces he doesn't know about.
Then there's traffic limitations - "dwarfs don't go outdoors", "absolutely forbidden zones" and other player-imposed restrictions, possibly applying differently to different agents.
Also, you might envision situation-dependent limitations - disallowing civilian dwarfs from moving through "enemy held territory", automatically maintained (rather than user-specified in detail).
What all this adds up to, I think, is that each path search is in principle unique, and we should have a system that permits arbitrary limitations to be placed on any individual path search. A path request could be as general as:
"Find a way from tile A to any tile with a limestone block; staying indoors at all times; going through no restricted doors except my personal room; walking, or jumping down no more than 1 z-level at a time; staying out of dangerous areas"
It's not as hard as it sounds, in principle: as has been stated already, A* can do all this - we just place custom limitations on which search nodes we are allowed to open. Whatever zone types we choose need to be annotated with the data we use for the limitations, naturally, but that will be obvious once we get there.
The tricky bit is that A* needs a connectivity map to be efficient. We can't maintain a connectivity map for each such custom request so we must find some way of cache the most commonly used ones, and compute an exact or approximate variation of the connectivity map when a special path request needs it. Requests for unusual restrictions are just that - unusual, so maybe we can get by with a flood fill every time for them. The more common ones ("general indoor worker dwarf walking through any unlocked door") will stay cached and updated constantly.
It's not a trivial problem but should be possible to solve, and with big dividends.
Finding good heuristics will be another challenge.