It looks like you will have to store your shortest path node list in memory somehow.
Also it seems that you need a bit more than brute force nearest nodes, you may need to exclude mountains and lakes, or assign appropriate values for hard-to-pass terrain.
So you may need to take that data you use for the terrain (i will call it "6 sphere face"), and use it to compute "shortest path node" only once (or only when it changes). This can be done and tested separately, until you get it right (even with smaller cube density if needed for testing purposes). In case of the corners, just allow null references for your nodes (if you need diagonal path too).
Every "shortest path node" may have a reference back to original "6 sphere face" node, so you get the real thing if needed.
This way your lookup algorithm remains simple and fast yet you do not loose any information about your world.
EDIT: As for adjacency of the faces, the most basic approach is naming things right. For example, of two futhermost corners of the box have respectively values of (-1, -1, -1) and (1, 1, 1), this information can be retained in cube face array. For example, cube face array may contain faces from (-1, -1, -1) to (-1, -1, 1) for U and from (-1, -1, -1) to (1, -1, -1) for V. A bit more math, but solving it would help to avoid a lot of repetition.