I would simply make the path finder assume all unknown areas are traversable. As the areas are discovered, you re-run the path finder. Eventually it will unveil enough of the map to find the path.

Of course, there's a possibility that the uncovered area of the map has a known possible path, but there's an undiscovered shorter path. You could tweak the cost of traveling through unknown areas to nudge the path finder towards or away from trying to travel through unknown areas of the map in case there's a shorter way.