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


  [1]: http://en.wikipedia.org/wiki/Expander_graphs
  [2]: http://en.wikipedia.org/wiki/Probabilistic_method