How do I solve a search problem on an infinite graph?
I believe you can use any algorithm for heuristic search.  On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.