I have a grid based A* that uses an unordered list (written in C), it is the slowest implementation of A*.

In a 695x132 grid test grid, it takes 15138 microsseconds to find a path from the uppermost part to the bottom (running on a core 2 duo 8400, ubuntu 32 bits). Realistically, the monsters (that use the pathfinding) can only see as far as 20 cells, so this is the maximum size of a path in my game (which takes 54 microsseconds).

Answering your question: A* is an algorithm find the lowest cost of going from one node to another, using edges as connections, in a graph. For this problem it is the fastest algorithm you can find. The problem of pathfinding is not the same problem as the one that A* solves, it can merely be reduced to it. So you can use particular properties of the pathfinding to improve its performance (for instance, if someone asks for a very big path, you can break into multiple smaller paths, you can reuse paths for units that are close to each other, you can have a region map to instantly solve unreachable paths and many others).

If I were you I would try a very simple A* implemetation and see how it goes, then either try to improve it or limit the action radius of the agents.

Check this http://qiao.github.io/PathFinding.js/visual/ out. Check out the jump point search, with preprocessing and future information that algorithm is very fast. So it all depends on the context. But A* is a good starting point in most scenarios.

^That's a pretty cool implementation demonstration.

One of the units may still require a short path to the player, but don't need it right now. I published the game and you can see me spamming here: http://www.gamedev.net/topic/642744-afv-hail-of-gunfire/