There are many examples in Alon and Spencer's The Probabilistic Method. One such example is the Cheeger inequality for graphs. Unfortunately for this thread, the canonical proofs which use the probabilistic method were originally written over 30 years ago.
