I believe in this specific case, there was a local optimum that random search (with the parameters we selected, which we actually tuned as well) was not able to escape.
In most cases I think you would find random search doing better than random parameters (unless we have the paradoxical situation you described), so your intuition is correct in the general case. But in this case there is no typo on the table!
Does this answer your question?
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?
It has much better guarantees than the method you used and tends to work quite well in practice. It's also probably what the reviewers meant by a random search baseline.
Reviewers asked for a comparison with this specific random search. You can go look at the reviews on OpenReview.