Although I guess you could have an infinitely large map and an algorithm that guaranteed connectivity. Infinite ways to fail to reach the goal. But I doubt there would be much practical benefit.

To actually answer your question it should be fairly easy to convert nearly any existing algorithm to cover an infinite area by simply tiling it. A common method to avoid boundary issues is to overlap the tiles slightly.