Clearly lack of a sound theoretical basis or proof for why deep learning works has not stopped its proliferation. For a practitioner, the proof is in the pudding: generalized results, novel solutions that provably work, new designs that fulfill the given objective(s). At the end of the day, those are what really matter for practical applications.
An important difference is the manner by which 'exploration' is codified in evolutionary algorithms, which allows for these algorithms to have a tune-able mix of hill-climbing and niche-finding. RL-based systems, Evolutionary Strategies, Swarm Intelligence, ... all are essentially hill-climbing and are typically much better at the 'exploit' aspect than the 'explore' aspect of the search. When you pair evolutionary algorithms with novelty search, for instance, you get very good coverage, as these guys have done with their sorting network work.
There are well known problems that evolutionary systems are much better at solving than NNs. The multiplexer problem, for instance, or sorting networks, where the search space is too rugged or deceptive for neural network solutions.