Finding any path between nodes of implicit, finite, regular, undirected graph
The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.