Randomized algorithm that "looks" deterministic? Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n.  There's no known polynomial time deterministic algorithm.  There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem.  But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are many possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness.  I realize that the question is probably not fully specified...
Shafi Goldwasser communicated to me that she and coauthors have been investigating exactly such algorithms for number-theoretic problems!  The following is known:


Lenstra has shown that there is such an algorithm for finding a quadratic non-residue mod a given prime.
Gat and Goldwasser have shown that there is such an algorithm for finding a generator of $\mathbb{Z}_p^*$, where $p$ is a given prime of the form $2q + 1$ for a prime $q$.


(I don't know of citable references.) There is also ongoing research on the question I asked about finding a prime between $n$ and $2n$.

EDIT: The paper by Gat and Goldwasser is now published: http://eccc.hpi-web.de/report/2011/136/. This paper though doesn't resolve the question of finding a prime between $n$ and $2n$.