NP-complete decision problems - how close can we come to a solution?

Question

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant approximation factor.

After we prove that a certain decision problem is NP-complete, what is the natural next step? Obviously we cannot "approximate" a boolean value...

My guess is that, the next step is to look for a randomized algorithm that returns the correct solution with a high probability. Is this correct?

If so, what probability of being correct can we expect to get from such a randomized algorithm?

As far as I understand from Wikipedia, PP contains NP. This means that, if the problem is in NP, it should be easy to write an algorithm that is correct more than $0.5$ of the times.

However, it is not known whether BPP contains NP. This means that, it may be difficult (if not impossible) to write an algorithm that is correct more than $0.5+\epsilon$ of the times, for every positive $\epsilon$ independent of the size of input.

Did I understand correctly?