Does this A-Star heuristic already exist?
This idea is called True Distance Heuristics and as you suspected, it can be very efficient.
True Distance Heuristics
True Distance Heuristics (as well as &quot;Pattern Database&quot;) is a technique that utilizes the memory to help with the search. The general idea is &quot;let us pre-compute a few important accurate distances, to save a lot of time during the search&quot;.
This is also sometimes referred to as &quot;Memory Based Heuristics&quot;.
Each technique has different memory requirements and require a different heuristic function (that, of course, may utilize the original heuristic function).  Also, some of course might be more beneficial in specific domains.
Differential
This technique suggests to choose k &quot;pivot&quot; states and store the shortest path from every state to each pivot
Canonical
This consists of 2 different data-sets:
Primary data: choose k pivot states and calculate all pairs shortest path among all of these k states.
Secondary data: From every node (out of all possible nodes), store distance to the closest canonical node.
Others
There are many other memory based techniques that uses this concept. Many prove themselves to be very beneficial, for a relatively small price to pay (in terms of space).
Food For Thought
As you suspected, these techniques can have admissible heuristics. Since it seems that you are interested in this field, I'll let you figure out the right heuristic functions on your on. I'll give you a hint that the formal proof uses simple math. Feel free to ask for these functions in the comments, and I'll answer.
I strongly suggest to draw these out in a simple drawing, it will make everything very clear.