I don't think that is correct.
Think the
pigeonhole principle you see in the Birthday Paradox would make the chances much higher than you think. I think the explanation you've given is how many times you would have to shuffle two decks of cards to have a 0.001% chance of them both being the same in that instance.
But what we want is the chances of any shuffled deck matching any other shuffled deck throughout history. Now after the first ever shuffle was done, the second had a 8x10(to the power of 67) to 1 chance of matching it. But the third ever shuffle in history now has two sets of previous shuffle orders it can match with, so the chance of the matching doubles the second shuffles's chances ( 4x10(to the power of 67) to 1), the fourth shuffle has three previous orders to try and match with and so on.
So with every new shuffle, the chances of matching a previous shuffle are reduced. Then you combine that with the number of attempts and the probability of any two, ever matching goes up quite quickly.