That means that its not doing any 'guessing', which is exactly the problem with A*.Dijkstra's algorithm is a special case of A* for an always 0 heuristic.
If you chuck a load of walls between the origin and destination it can screw up the heuristics resulting in an estimated distance that is much less than actual distance needed to reach the target.
The only way to truly be exact is to not use heuristics, although that is a lot slower.
 also you have not explained how you would model the terrain cost into the heuristics.[/edit]