I think you may have overlooked a logical solve. I dug into the code for his Minesweeper at one point and IIRC it works by generating random boards and putting them through a deterministic backtracking solver that gives up when faced with one of these choices. I think it then has a way of changing the board to be solvable. Or it just generates a new one, I don't remember.

I've also played it quite a bit and can't remember having any undecidable boards.