Earlier quoted context omitted.
Ask anyone who's ever worked on an RTS and they'd disagree with you. It's not even difficult to find evidence to support them being tough problems by googling it: https://www.google.com/search?q=rts+pathfinding Lots of people asking for solutions, lots of different solutions, lots of caveats.
Even without any search, you can come up with a lot of problems: Will you calculate an alternative route as soon as a route gets blocked? What if it is a friendly unit? Should it move to open way? What if it's already moving? What if it's too slow? What if there are more, moving to different locations with different speeds and priorities (For example: A tank going to help defend the base vs. a resource gathering vehi…
For starters, yes there are complex problems with lots of edge cases indeed. But not one of the many problems you suggest are computationally difficult. Now there are some computationally difficult problems to deal with in an RTS but those are not among them.
Additionally, a large amount of the problems you just listed are common among any game with AI. RTS pathfinding is hard, but so is pathfinding an an FPS, and then add in how much more complicated a level is in a game such as Assassin's Creed, to the more simplified structures you can manage in an RTS, and it's easy to see why this isn't simply a matter of RTS games being simply more difficult.
And within an RTS there very many problems that are much easier, both from a complexity, and computationally then in other games. Visibility determination is one thing in particular that's considered super difficult, and very performance sensitive, that's very easy to solve with the fixed perspective of an RTS.
And then there is networking, in which case you can use a lock-step model in RTS due to being less sensitive to latency, that both vastly simplifies networking. And also makes it possible to synchronize the large amount of units in an RTS with minimal bandwidth.