Randomized algorithm that "looks" deterministic?
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$.