Not sure about differences in PC's, but my A* implementation finds path on 400x400 maze field that stretches from one corner to another in ~7 msec.

There are many different reasons why your A* implementation may not perform well. The most common reasons in my experience have typically been:

1. Using the wrong heuristic
   
2. Poorly managing the open list (for example, using a slow sort or next-best search)
   
3. Having a closed list.
   

Make sure you're using the correct distance approximation heuristic for your map. For 2D tile-based games Manhattan distance is usually a good heuristic.

If you can avoid iterating over the entire open list each time you need to check the next grid cell then do so.

Also, you can optimize away your closed list of cells by instead adding a closed flag to your map for pathfinding. When you start a pathfinding operation you reset the flag on the entire map (you can actually avoid this step by using an integer flag, but that's probably not necessary). Whenever you close a cell, instead of adding the cell to a list, you just set the flag. This will enable you to check if a cell's closed with a simple lookup instead of having to search. This does depend on you being willing to add this flag to your map, which does violate some principles of encapsulation and may offend some of the stricter coders out there. You could instead allocate a separate structure for this maintained by your pathfinder, but you'd have to make sure your structure always matches that of your map. Implementing that separation could be more trouble than it's worth.

OP, probably one of the most overlooked optimizations for a* is that instead of maintaining seperate open and closed "lists", have a 2d array of chars that represent the state of a node (0=n/a, 1=open, 2=closed, 3=unpassable), with a seperate 2d array of uints for important node-specific statistics such as distance travelled.

Another extremely useful optimization is to use binary heaps to sort your open list values. I recall that when I tested the binary heap sort versus the std::list sort, the difference in speed was half an order of magnitude, even when there were very few values in the heap which is one of the binary sorting algorithm's weaknesses.