Efficient pathfinding without heuristics?
Complete and Incomplete Algorithms

Search algorithms can be classed into two categories: complete and incomplete. 

A complete algorithm will always succeed in finding what your searching for. And not surprisingly an incomplete algorithm may not always find your target node.

For arbitrary connected graphs, without any a priori knowledge of the graph topology a complete algorithm may be forced to visit all nodes. But may find your sought for node before visiting all nodes. A* is a complete best-first method with a heuristic to try to avoid searching unlikely parts of the graph unless absolutely necessary.

So unfortunately you can not guarantee that you will never visit all nodes whatever algorithm you choose. But you can reduce the likelihood of that happening.

Without pre-processing

If you cannot consider pre-processing your graph then you're stuck with a myriad of on-line algorithms such as depth-first, breadth-first, A* and greedy-best-first. Out of the bunch I'd bet on A* in most cases if the heuristic is even half good and the graphs are non-trivial.

If you expect all routes to be short, a breadth-first algorithm with cycle detection and duplicate node removal may outperform A* with a poor heuristic. I wouldn't bet on it though, you need to evaluate.

With pre-processing

In your case I'd see if I could pre-process the graph, even if you need to repeatedly re-do the pre-processing when the graph changes as long as you do sufficiently many searches between pre-processing it would be worth it.

You should look up Floyd-Warshall (or some derivative) and calculate the pairwise cost/distance/jumps between all nodes and use this table as a heuristic for your A*. This heuristic will not only be admissible, it will be exact and your A* search will complete in no-time.

Unless you of course modify the algorithm to store all pairwise routes as they are detected in a matrix of vectors, then you have O(1) run time at the cost of memory.