If it were just up to randomness with an unmodified ROM, then (barring a glitch) they would have soft locked at the Safari Zone which costs some currency to enter and needs to be traversed to the Surf HM in a relatively tight number of moves. There's only a finite amount of money in the game, so they can only fail at most a few hundred times before the game becomes impossible to beat.