CS theory has a slew of these examples. In particular, take any problem which is known to be in $RP$, but its membership in $NP$ P$ is (currently) unknown.
Example: is it possible, using walks consisting of polynomially many steps, to estimate the volume of a convex body?
In the terminology of your question, the answer is 'yes' if you say that random steps are a reasonable model of the steps made by a smart algorithm. On the other hand, a deterministic method of choosing the steps is unknown.
(PS the reference on this particular problem is "A random polynomial-time algorithm for approximating the volume of convex bodies" by Dyer, Frieze, Kannan.)
