I'm not sure I agree with that, the mechwarrior talk was pretty informative and the variability of terrain and dynamic obstacles made for some interesting challenges. It was particularly interesting when they talked about 'squad walking.' (going into a line in tight spaces etc) When I was thinking about writing my own RTS I did some simple experiments and certainly got a feel for it being quite complicated.
Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.
What you are describing is the complexity for a single path. But there are lots of units that need to be placed and have their paths potentially interact to achieve some goal. This seems very analogous to circuit routing.
Maybe it's too simplistic but in the vein of the outrageous hack I like it.
[1] http://www.teamliquid.net/blogs/viewblog.php?topic_id=306999
Circuit routing is an entirely different beast. A previously routed "shortest" trace from one node to another can obstruct a much shorter trace between two unrelated nodes. In this way it's similar to the traveling salesman problem, where early "greedy" choices made by the salesman can force him to make much less efficient choices later.
I remember circuit routing was an example in Skeina's Algorithm Design Manual [1], and believe he proved that it was indeed NP-complete, not polynomial like the general pathfinding problem.
1. http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...