How to get initial flow for TSP with missing edges
Set the cost on the missing edges to $+\infty$, or some suitably large constant.   Then all paths are valid, and you can apply simulated annealing.  Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time.  That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph.  Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path.  (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)