But while searching on a strict grid, it DID (always) find the shortest path.

What do you mean by understating values? Could I do some trick with the move-cost for a connection (now I use simple distance) to lessen the errors?

Or could I manually lessen the optimization to increase precision (without rebuilding it fully into djukstra).
It seems to already optimize the NUMBER of nodes in a path (to have the least steps).