Map is a grid. Grid is a graph. A* works on graph, it is a graphs searching algorithm. A* should search few nodes of graph.
As has been mentioned they can use navigation mesh. But the A* (or something similar) will be on top of that mesh anyway, because polygons of this mesh are just nodes of a graph; A* will then search for path from one polygon to another polygon.
Not sure about Warcraft or commercial games, but there is also technique called Collaborative Diffusion and it is very simple; it is usually done on grid. There is also technique called Potential Fields, which is very similar to previous one if not the same.
You might also try:
- whether some of these games have source code available
- whether some of clones of these games have source available
- whether SDK or editors don't hint something
- ask employers of companies making these games, some of them might be willing to share