Tbe only problem I have with A* is that it has to look at every square on the map to detect a fail and it can slow things down a little bit.
The something is wrong and suggest your heuristic is not set correctly. What you describe is Dijkstra's Algo. this is very good at describing the different methods.
p.s. Depending on the type of map you can also use Steering Behaviours to do pathfinding.