Problems in P with provably faster randomized algorithms
Polynomial identity testing admits a randomised polynomial time algorithm (see the
Schwartz-Zippel lemma), and we currently don't have a deterministic 
polynomial time or even a sub-exponential time algorithm for it.

Game tree evaluation Consider a complete binary tree with $n$ leaf nodes each
storing a 0/1 value. The internal nodes contain OR/AND gates in alternate levels.
It can be proved using adversary argument that every deterministic algorithm
would have to examine $\Omega{(n)}$ leaf nodes in the worst case. However there is
a simple randomised algorithm which takes has expected running time of $O(n^{0.793})$ 
Look at slides 14-27 of the talk. 

Oblivious routing on a hypercube Consider a cube in $n$-dimensions containing
$N=2^n$ vertices. Each vertex has a packet of data and a destination that it
wants to eventually deliver the packet to. The destination of all the packets
are different. Even for this, It has been proved that any deterministic routing strategy would take $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ steps. However, there is a simple
randomised strategy which will finish in expected $O(n)$ steps with high probability.

Note that in randomised algorithms, the expected cost $E(F(n))$ with high probability (like for eg. $Pr[F(n) &gt; 10 \cdot E(F(n))] &lt; \frac{1}{n^2}$) is
equivalent to worst case in practice.