He is referring to the probability that this specific shuffling has come up before, not the probability that there have ever been two shuffles with the same res

He is referring to the probability that this specific shuffling has come up before, not the probability that there have ever been two shuffles with the same result (which is where the birthday paradox comes into account).