This paper initiates the study of probabilistic (polynomial-time) search algorithms that with high probability output the same solution. That is, for a fixed relation $R$, such algorithm (called Bellagio) associate a "canonical" solution (denoted $s(x)$) with any instance $x$ (which has a solution) such that $prob[Bellagio(x)=s(x)]>2/3$. Of course, such an algorithm is of interest only when no deterministic (polynomial-time) search algorithms are known.
The paper shows several such examples as well as establishes the a necessary and sufficient condition for such algorithms: A relation $R$ has a Bellagio-algorithm iff finding solutions wrt $R$ is deterministically reducible to some BPP set.
The first direction is proved by using the reduction as an algorithm, while providing answers to its queries via a BPP algorithm (of sufficiently low error probability). For the opposite direction, suppose that $A$ is a Bellagio-algorithm for $R$, and consider the set $S$ s.t. $(x,i,b)\in S$ iff $\prob[A(x)_i=b] > 2/3$. Then, (i) $S$ is a BPP set, and (ii) finding solutions wrt $R$ is deterministically reducible to $S$.
In contrast to this fact, in my work in the world of P=BPP, it is showed that a natural class of "BPP search problems" is deterministically reducible to "promise BPP". Thus, the difference between standard problems in BPP and promise problems in BPP seems crucial. Indeed, using a deterministic reduction of search to a promise problem in BPP does not seem to yield a Bellagio-algorithm; the problem is that queries that violate the promise may yield arbitrary answers, which may possibly lead the search to different solutions...
See ECCC TR11-136.