I think a more salient point than "Bob only has to do the work once" is "Bob has done the work ahead of time", no? In fact, even in the long run, Bob is doing a lot more work than necessary (computing inverse one-way functions for all/most possible inputs). It's just that he's preemptively computing them.
The point is he wants to look-up more than one example because the crossword contains several words. Going though the full dictionary N times is harder even if on average he only needed to try half of it than doing it once.
