Read the thing, it explains that their "perfect shuffle" isn't every card being perfectly interleaved (yes that'd be deterministic).
But rather, at every card, there's roughly 50/50 chance of it being a card from left/right piles being dropped, with an increasing odd for the bigger pile.

I haven't bothered proving it, but I'm pretty sure a perfect intellect interleave would eventually put the deck back in order, but that's not what the article is discussing.

Yet terms and conditions also apply. One: The riffle shuffle has to follow a realistic but strict model where cards are randomly interleaved from the left or right pile one by one. (Each card gets dropped from either the left or the right pile with a probability that’s proportional to the number of cards remaining in that pile. This means that the cards don’t simply alternate between left and right, which would result in a predictable structure; instead, the order might go “left, right, right, left, right, left, left.”)

Two: The deck has to be cut more or less in half before shuffling.

“All of our analysis depends on those details,” Diaconis said.

"Perfect" in this context should be read as something like "perfectly random", i.e. like a computer program with an RNG would do it, and not like a fallible human would do it. You're right that using a certain algorithm with a certain seed would reproduce the same result.

In other words, think of it like running your computer program, but with a true RNG that uses radioactive decay to determine which pile is selected from next. That's the sort of perfect randomness the paper talks about.