This is actually part of the reason why people complain about the approvals process.

Your entirely legitimate app will get rejected for some confusing, badly described reason you have to guess at, meanwhile an obvious rip off with terrible functionality slides through without comment.

I think there are two problems here:

First, a skewed distribution of "wheat" and "chaff" apps. I would bet there are at least 10x as many "chaff" submissions as "wheat" submissions. Passing that distribution through a classifier with 90% precision and 90% recall will result in "only" a 50:50 mix of wheat and chaff apps in the app store.

Actually, I could easily see the skew being 100x simply because nothing really stops a malicious actor from hiring 100 different mules to create 100 different developer accounts and submitting the same malicious app until it randomly passes review. Having only a 50:50 mix of apps now requires 99% precision and recall.

Second, the principal-agent problem. I would bet the amount of app store reviewers who are receiving bribes is not zero, and further that bribing app store reviewers is probably among the highest marketing ROI spend that fraudsters do. Apple/Google can randomize who reviews which app, but how many reviewers do they have? If I bribe one reviewer, how many copies of my malicious app (see previous paragraph) do I need to submit before one of them is routed to "my" reviewer? Probably not many.

Even with honest reviewers, I'm sure reviewers have some kind of daily quota they have to meet. If you're behind quota, are you going to carefully review an app, or reject it for tenuously-applicable reasons? That annoys app developers, but does the reviewer care? No, they hit quota, which is all that matters to them.

I'm sure someone will reply "well, Apple/Google should just ____". I hear you, but your proposal is either going to be much more expensive, much slower, or result in more bad apps being approved. In other words, it's likely that the current system is (nearly) pareto-optimal.

Exactly-- they don't care about the product, only a process they designed to weed out vendors for obscure technical reasons. You can have a store that prizes quality (as defined by users) but Apple doesn't care about that. Instead they emphasize things like the use of whatever new SDK feature they created.

Or the shovelware vendors are just more willing to jump the hoops. In once case we (our legit app) just stopped jumping - because it wasn't strictly necessary to our revenue stream. Perhaps the shovelware-clones have different view of the payoff-function for the work. And so jump all the hoops, or have lots of practice navigating that minefield.