Well, this particular method can be defeated by running a primality tester first. Still, it's important that the problem you're solving in this method has a solution (or a short proof of lack of a solution) which I think restricts us to problems in the intersection of NP and co-NP.