Longest Path A*, Admissible Heuristics, and Optimalness
It seems to me (and correct me if I'm wrong) that a regular A* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're searching for the shortest path we want a heuristic that will never lead us down a path that will be longer than what we estimate it to be, in your case you never want to be led down a path that will be less than what you estimate it to be (which you say you have). 

A heuristic is a function that gives $h(n) = 0$ at the goal.

An admissible heuristic is one that never overestimates the distance to the goal. In your cause you want the longest path rather than the shortest, so an admissible heuristic never underestimates the distance to the goal. 

So if you have a heuristic that gives you at least the correct distance from the current node to the goal node or a larger value and you order your queue by largest $f(n)$ then you have a correct implementation of A*.

On the other hand if your heuristic both may underestimate or overestimate you're aren't guaranteed to find an optimal path.

We can prove the optimality of this easily (this is an adapted proof from Russell and Norvig's Artificial Intelligence A Modern Approach).

Let $G$ be an optimal goal state, with path cost $f^*$. Let $G_2$ be a suboptimal goal state with path cost $g(G_2) &lt; f^*$. Now assume that A* has selected $G_2$ from the queue. Because $G_2$ is a goal state it would terminate the search with a suboptimal solution.

Consider a node $n$ that is a leaf node on an optimal path to $G$. Because $h$ is admissible (never underestimates), we must have

$f^* \leq f(n)$

And if $n$ was not chosen over $G_2$ then

$f(n) \leq f(G_2)$

Combining these we get

$f^* \leq f(G_2)$

Because $G_2$ is a goal state $h(G_2) = 0$ thus $f(G_2) = g(G_2)$. So we have a contradiction that $f^*$ is an optimal longest path and that $G_2$ is suboptimal. Thus A* will never expand a suboptimal solution and is an optimal algorithm.