Well you need to separate your sphere mesh representation from the node representation anyway. As long as you know which face is across from the cube edges it is pretty easy to build the adjacent node list. Using just 4 neighbouring nodes eliminates the 7 neighbour problem at the corners too.
yes I understand now, it's going to be a pain getting the nodes from each adjacent face as rotation of the face as well as its adjacency to the "active face" will have to be calculated in order to return the correct edge. Would using just 4 neighbouring nodes make the algorithm much slower?
The less neighbouring nodes the faster the algorithm will run but the path won't be as optimal.
You only need to calculate the node connectivity information once. Try doing it with a 3x3 node layout per cube face first, it should scale up easily after that. You can always draw the network to check you have worked it out correctly.
Don't worry about impassable terrain or terrain with high movement cost at first, just get the network setup correctly. It's easy to add a prohibitively high cost for moving from one node to another if it is blocked later on.
You can optimise lookups once you have the network by having a 2d array of precalculated "next nodes" to travel to (will use a lot of memory if the number of nodes is high though). Say you want to go to node D from node A, and the optimal route is ABCD. Store B in the table for entry (A, D) i.e. the next node to travel to from A. The next node for travelling from B to D would then be C, so store that in the (B, D) entry. (You'd store C in the (D, A) entry assuming optimal route from D to A is DCBA).