Well, it's never random, is it? It's only random when all is equal, otherwise it's biased. That's why it works.
Consider birds. There was a good article a few days back, on why only non-toothed birds survived. Until the meteor-strike, 65M years ago, all was equal and they survived along-side. Until they were the only survivors.
Except where punctuated by (subjective) catastrophe.
But then it is not the mechanism of evolution itself that is random.