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.)