I’ve come up with two ways of doing it, if any of you are still interested in this problem.  Both have worse computational-complexity than BFS/Djikstra’s, but may still be faster in practice on large graphs or graphs with many obstacles.  I’ll try implementing these if I can't find anything better, and see how they compare to BFS for my problem-space.

The first way is more widely applicable.  The second is specifically for 4- or 8-connected graphs with all edge-weights 1 (or infinity).

The problem, again, is that there may be multiple best-paths, and we want to use A* to find the same path obtained by BFS/Djikstra’s.  To do this, we must alter A* slightly – instead of stopping when we reach the end-node, we continue expanding all nodes with f-value <= f(end-node).  Since the A* heuristic is admissible, this guarantees that all nodes that belong to a best-path will be expanded eventually:  in particular, the nodes belonging to the BFS-best-path will be expanded.

In the first algorithm, when a successor B of a node A is seen for the first time, we set its distance-to-start g(B) = g(A) + c(A,B) and its previous-node property p(B) = A, like usual.  If B is also a successor to node C, and later C is expanded, we compare B’s current distance-to-start g(B) with its potential new distance-to-start g’(B) = g(C) + c(C, B):

    If g’(B) < g(B) (only possible if h is not consistent), we overwrite g(B) and p(B)
    If g’(B) > g(B) we do nothing.
    If g’(B) == g(B), we have a problem.  We need to figure out which path has higher lexicographical ordering - we need to find the first node that the path passing through A and the path passing through B deviate from one another.  Once we know that, we can simply check which path takes the higher-priority direction from that node.


Finding the first node that the paths deviate is simple enough:  we walk backwards along each path's previous-node property p(n) until we find the first node belonging to both paths.  Since every node has only one previous-node property, every node before this one will be the same on both paths.  Since this node will have the same g(x) value for both paths, we can find it by always stepping backwards on the path with the higher g(x) value.

If C is considered part of the current best-path at this point in our algorithm, and both B and C (or A and C) are part of the BFS-best-path, then B (or A) will be considered part of the current best-path at this point in our algorithm.  And since all best-paths start at the same node, we can show inductively that this will give us the BFS-best-path.

The second algorithm is similar to the first, but we use the fact that, since there is (thus far) exactly one node where the paths containing A and B go from being the same to differing, instead of searching backwards from the end for the first place they're the same, we can search forwards from the start for the first place they're different.  We can do this by storing the entire best-path found so far for each node in that node.  In most cases, this would be unwieldy, but in 4- (or 8-)connected graphs with all edge-weights at 1, we can store the best path using 2 (or 3) bits-per-node, with higher-priority paths having higher values.

We can treat the paths as arbitrary-length integers, with the most-significant-2-bits representing the first direction moved.  Then (assuming the two bit-strings have the same length) we can simply check which integer is larger to determine which path has higher priority.  This allows us to compare 16 nodes of the path at a time with 32-bit registers; 32 nodes with 64-bit registers; and 64(!) nodes at a time with 128-bit registers (like the SSE registers in x86 and x64 processors), making this search very inexpensive even for paths with 100's of nodes.

---

As I was writing this, a user on Stackoverflow.com posted a third potential solution:  run A* as above to expand all nodes that belong to a best path; work backwards from the finish to find only those nodes that belong to a best path; work forward from the start again, finding the BFS-best-path by walking along the nodes that belong to a best-path, always moving upwards in g-value and breaking ties using our lexicographical-ordering.