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.