That sounds great, in theory! One thing I've found to be the case after making the switch from web stacks to gamedev is that theory is quite often a very different ballgame versus the practical application of the theory.
For turn-based games, absolutely -- and I suspect that's why you rarely see pathfinding brought up as a big concern for turn-based games. They have plenty of time to re-compute paths, there's a perfect sequence for map invalidations, etc... But for RTS or simulation games, the latter being where I draw my experience from[0], it's really a different beast -- you touched on some of the reasons why, such as map invalidation & larger total scales (units, nodes, commands, etc).
What happens is, you do this -- and then you fire up a build and find that the game freezes every time you need a path. Okay, let's get some concurrency going -- easy! But how are we going to handle map invalidation/sync between threads? Definitely solvable. Then you find, it's still too slow -- thread overrun! You can't do realtime pathfinding for 500 units through 100k nodes, why not? Is it the sync/concurrency locks?
Meanwhile, you've spent all this time trying to get perfect paths to run fast and you could instead be working on what the gameplay needs; maybe that's pathfinding related too, perhaps some units should only be able to use paths that have 5x5 clearance while others need 10x10, etc... How do you deal with nodes that are unreachable -- do you allow the pathfinder to explore the entire terrain, only to find there aren't any paths? Sure, you can do some initial exploration first; but perhaps 'reachability' differs per unit-type, or maybe you have uni-directional traversals, etc. Or how about avoiding other units? Etc... :)
Pathfinding generally isn't really that difficult to get to an MVP implementation of; but it IS hard to get something that is anywhere near "perfect", for every single case, and especially if it needs to be realtime or if your map changes.
The requirements inevitably continue to add up (out of gameplay necessity, not client demand per-say), and each respective aspect of it nearly always takes an incredibly large amount of time to implement, test, debug, and ship.
FWIW, our game[0] implements ~5 fairly distinct pathfinding "approaches" to deal with various situations like these (windowed, various levels of hierarchical / JPS, vanilla A*, cooperative, etc), some with more "complete-ness" than others. I can assure you that it's anything but pure theory-craft, and honestly it can sometimes be fairly difficult to reason fully reason about it without trying things. That's another awesome thing about gamedev, though also a negative as well -- sometimes you can "reason yourself to death" and it's often better to form a high-level plan and then give it a try, so you can quickly see where the holes in your approach are & and how surmountable (or not) those pitfalls may be.
In any case, I think my point can be largely summed up by saying that it's likely very often a case of "easier said than done" when truly considering the entirety of the problem. One final thing to consider is that, when it comes to games, allowing a failure case (or a full-map expansion) is basically a no-go -- the last thing you want is for a player to see a stuck unit, or a frame drop, and in that way it's very much an "all or nothing" exercise. :)
0 - Co-Creator & developer of SimAirport http://store.steampowered.com/app/598330 (in Early Access & under continual active development)