Today I learnt that A* doesn't work for an arbitrary non-planar graph, you need additional structure:
https://stackoverflow.com/q/26568552/509706
This matches my experience with difftastic so far. The graph is non-planar and my best heuristic only matches Dijkstra perf in typical cases.