How could you have a local optimum with random search? It's not doing any hill climbing or anything so it shouldn't care at all about local optima. Yes, of course you could get bad results if you specify the random search distributions with too strong of a prior pointing in the wrong direction, but we usually specify a weak prior (uniform/etc distributions) for doing random search. What random distribution did you use for your random search?

Anyways, if you had a bad random search prior, then that should have equally negatively impacted your random parameters as both should have been drawn from the same distribution. If you used a different random distribution for random search vs your "random parameters", why did you use a different distribution and why were they so different?