As Scott Aaronson points out, the easy solution to this is that you add a slight quantum chance that the algorithm will yield "Reject". As long as that chance is non-zero, but greatly smaller than the probability of any particular successful permutation, you will survive in the universe that says "Reject".