I find Shannon's use of random codes to understand channel capacity very striking.  It seems to be very difficult to explicitly construct a code which achieves the channel capacity - but picking one at random works very well, provided one chooses the right underlying measure.  Furthermore, this technique works very well for many related problems.  I don't know the details of your Example 4 (Erdos and Ramsey numbers), but I expect this is probably closely related.