I'm not certain I understand your argument. If the algorithm works, why should I care? Chess isn't played by evaluating all viable moves in a minimax tree to a depth of x ply either, but that's how Deep Blue did it.

Not that the two are mutually exclusive. In order for a proof-based algorithm to work, it'll need to avoid risky moves until it has sufficient information to be certain where a mine is.