It gets better with practice as you develop more accurate intuition. Eventually, most new ideas that you try will work, but it takes a lot of failures to get to that level.
Well, maybe. It isn't entirely clear just when that anecdote happened (he was at Google first as an intern, then as a research scientist, then he was at OpenAI before going back to Google).
In any case, as important as a developed intuition is, it is no guarantee that it will provide the necessary insight after hearing a description of the problem rather than experiencing and digging into it himself.