Games of hidden information are very weird in their randomness.
Minesweeper, of course, is well known to be annoying for its randomness, which is why I went to the effort of writing a version that didn't require random guesswork. When you have no choice but to take a risk, it's annoying to be wrong because it terminates your game.
But I've recently been sent an implementation of the puzzle/board game ‘Mastermind’ for my puzzle collection, and I've been finding that the annoying randomness works the other way in that: it's much more annoying to be right. When you've just constructed a guess which you've carefully designed to narrow down the possibilities and bring you one step nearer to the actual solution … it's terribly irritating if that guess turns out to be the exact answer. In a game played against an opponent, where each of you was scoring points for how quickly you solved the other's problems, this would at least be useful to you because you'd get a lot of points for it. But in a solo context, you're not really after the high scores; you're after the satisfaction of reasoning your way to the answer step by step, and to unexpectedly hit the right combination at an early stage rather spoils the fun.
That continuous refinement step, if done in either Guess or Mines, would make the game deterministic: if you make the same sequence of guesses, or click the same sequence of spaces in the minefield, the solution will always be the same. I doubt this is a good idea.
Fundamentally, I suspect the real problem is just that Guess is a much simpler game than Mines.
I suppose you could take it a step further (as John might or might not have intended to imply) and deliberately choose a mark to return which will rule out the fewest of the combinations still in the list; that might run a greater risk of leading to determinism and would therefore presumably be undesirable. (Though it might still not become completely deterministic: in situations where there are two joint-nastiest marks you could return, you would probably still want to pick randomly.)
Perhaps a sensible middle ground would be to examine the full range of marks you could legitimately return for the current guess, rule out a few of the ones that provide tons and tons of information but leave most of them still present, then pick at random from them (possibly weighted by the number of combinations scoring each one). This might strike a plausible balance between avoiding determinism and also avoiding disappointingly short games (since being entirely right isn't the only danger - being almost entirely right is almost as bad).
I suspect I'm not actually going to get round to trying this, but I don't think it's fundamentally infeasible in principle. (Though I do agree with you that it's taking the idea quite a lot further than I did in Mines.)