In other words what is the probability that Bob has lied about the Merkle root after N queries?
Well, here is one way Bob could cheat; he could take the list of $M$ values $$V_1, V_2, ..., V_M$$ and instead of forming a Merkle tree based on that, select a value $c$ index and a value $V'_c \ne V_c$, and instead form the list $$V_1, V_2, ..., V_{c-1}, V'_c, V_{c+1}, ..., V_M$$ and form the Merkle tree based on that list (and give Alice the computed root, which is with quite high probability different from the root from the original list).
Then, when Alice gives him the $K$ indices to base the $K$ proofs on, he forms them based on the modified list and the tree he computed. He will be detected as cheating only if one of the indices she asked for happens to be the index $c$; if none of the indices she asked for happened to be for index $c$, then the proofs she would receive are all valid and consistent with each other (as they correspond to a self-consistent Merkle tree, with the revealed leafs being the values she expects)
The probability of Bob being caught cheating, that is, the probability that one of the indices Alice picked is $c$, is $K/M$. Hence the detection probability against any strategy is no more than that (it might be less if there is an even better strategy Bob could employ).
So, to detect Bob cheating with probability 0.99, we have $K > 0.99M$; at that point, it'll actually be less computation for Alice if she were just to recompute the tree herself.
Seemed interesting to us because it could be a form of proof-of-space-time if the list is expensive to construct
Now, looking at the problem as a proof-of-work is a bit more interesting (proof-of-space doesn't work, as the tree and authentication paths can be computed without increasing the amount of computation required significantly); obviously, the cheating strategy I gave above doesn't break that problem, as Bob is doing the full amount of work. If I had more time, I'd try to investigate that more...
