Of course you could also pull out the good old Chomsky hierarchy and make an argument against regexes based on whatever the nature of your data is.

But the thing is: the beauty of regexes lies in their compactness (which, in turn, can make them quite difficult to debug). So, of course, if you want to optimize for some other measure, you'd use an alternative approach (e.g. a parser). And there are a number of worthwhile measures, such as e.g. the already mentioned debuggability, appropriateness for the problem at hand in terms of complexity, processing speed, ease of using the match result, the ability to get multiple alternative matches, support of regexes in your language of choice, etc.

But simply stating "X beats regexes" without saying in what respect leaves something to be desired.