Look at my task 442E - Gena and Second Distance. There are some technical details in realization which make it not so cool, but there is still an interesting idea of how we can decrease complexity of algorithm (you can read it in editorial).

There was a problem from IOI 2016 practice tasks saying:

There's a string S of length N containing 1s and 0s only, you don't know the string but you know N (N<=1000), you can ask at most 1024 questions: is P a substring of S? then you have to know the string S.

even though it has deterministic solution but if the questions are guaranteed to be answered honestly then a nice randomization solution exist

I remember solving this task from NCPC 2014, Basin City Surveillance, using a randomized backtrack algorithm.

Here is a solution to another problem solved with randomization.

Smallest enclosing circle is a classic example of randomization. In "higher algorithmics" there are lots of randomization algorithms, for example a lot of color coding techniques like "k-path", "triangle packing", "d-clustering". You can also search for applications of isolation lemma which is some prob lemma that is used to estimate success prob in various randomized algorithms.

Moreover, you can view it as a lame kind of randomization, but technically speaking all polynomial hashes etc are also technically speaking randomized algorithms. Another funny example is checking if there is a perfect matching in bipartite graph by creating an nxn matrix denoting adjacency matrix, but with ones replaced with some random numbers modulo some big prime number P. Then you calculate its determinant and if there is a perfect matching you get nonzero number with very high prob and if there is no such you get zero. Maybe this one isn't so impressive because problem we wanted to solve is pretty easy using standard methods, but you can use similar idea for any graphs, not just bipartite, but you need something more clever called Tutte's matrix.

You might wish to see Freivald's Algorithm which is a probabilistic randomised algorithm to verify matrix multiplication in O(n^2) time. (You might probably know it!! :D)

I recalled one more example. Problem C here http://mirror.codeforces.com/gym/100203 is probably a completely different randomization approach than those you have already seen. Very similar idea shows up in a "Conway" problem from Petrozavodsk Winter 15 Moscow SU Tapirs Contest (which was, unsurprisingly, unsolved during actual contest).

This problem is pretty neat I think: Pizza Problems But just by simply posting it here the solution is kind of semi-spoiled. ^^

I summon Gassa and Burunduk1 to share their expertise about randomized algorithms and problems.

Some suggestion:

444B — DZY Loves FFT

329C — Graph Reconstruction

http://mirror.codeforces.com/gym/100512 J

This is a relatively simple problem from regional school olympiad.

Given a set of points, it's known that these points are lying on not more than two circles. You are to determine the coordinates of centers and radiuses.

This one has randomized solution : https://www.codechef.com/IPC15P2B/problems/NOPI
Not sure if you consider it nice task though.

I suggest you to check long algorithm contests, like Topcoder Marathons. As to my knowledge, all the top solutions from the past are randomized there. One of the latest tasks featured a problem that could be reduced to modified TSP, for instance.

Another one from Bubble cup finals. 717H, Pokermon League Challenge

Given a connected undirected graph, find number of pairs of edges such that graph becomes disconnected when these two edges are deleted.

Finding Lines from NWERC 2014.

Colinear From Atcoder contest. After 8 years from your post a problem finally came on atcoder contest