I remember there was a paper co-authored by one of the inventor of genetic algorithms. They tried to come up with a toy problem that would show where genetic algorithms definitely beat hill-climbing. The problem they came up with was extremely contrived. But a slight modification to hill-climbing to make it slightly less greedy, and it worked just as fine or better than GA.

Statistics and machine learning are still poor at the problems that GOFAI does well on.

We are just starting to see ML successfully applied to search problems. There was a paper on deep neural networks that predict the moves of Go experts 45% of the time. Another paper found deep learning could significantly narrow the search space for automatically finding mathematical identities. Reinforcement Learning is becoming increasingly popular, which is just heuristic search, but very general.