From what I can tell and tested out, his grab doesn't stale at all. In the video, the the characters who couldn't be infinited simply with a down throw were ones who had more traction than the heavier characters, like Donkey Kong and Bowser.
After viewing this, I tested it myself. But instead of doing it exactly like the person in the video did it, I tried character who shared traits that the Samus, Mario and Luigi have.
That being said, I tested it on Marth, Jigglypuff, and Wario, who all have lighter jumps and/or lots of ground traction. All failed, because they slip too far away, the person who I actually came closest to infiniting was Wario, but I had to dash after him immediately after the throw, the stagger period that Wario has after begin thrown is big enough to accomplish this.
I tested it again with Peach, Ike, Fox, Sonic and Ganondorf, all failed, and Ike and Sonic had the same thing that Wario suffered from. But the one thing that caught my attention was Fox, who just simply fell down after being thrown, in contrast to the other subjects where they landed on their feet and slid but a small distance.
This made me deduced one thing that helped me complete my research, that escaping from an infinte depends on two traits that a character must have.
A. The perfect ground traction.
B. A various range of speed decents/speed of aerial movement.
These are the two factors on why Samus, Mario and Luigi are hard to infinte, because their ground traction, and aerial movement/speed of their decents are within the proper range to just barely get out of an infinite.
Barely. But this was a hypothesis.
Next to continue my research, I picked Luigi and noticed exactly what the video pointed out, so I started to test distance, in terms of if the range got shorter, I get Luigi at the edge of the stage, set perfectly so if he was to fall off, he'll grab the ledge and I'll just press forward to reset his position, I let Dedede stay at a precise point in front of Luigi, indicating his spot by the pattern in the stage. I noticed that Dedede could still grab him at the furthest possible distance, but still could not do an infinite. So with this, the range of the grab is ruled out.
Next, I went to training mode, and I put Luigi and Dedede in the exact same positions they were in before, but this time I set the speed to 2/3.
And I tried it again, at such slow speeds, observation is much easier to the naked eye. I noticed that the time before Dedede's throw and the regrab didn't change at all speed of the regrab wasn't it. I also spotted that the distance never changes after the grab and throw, so distance is also moot. What I did notice, was that Luigi got some free invincibility frames after the throw, thus changing the timing of the throw after a while, but, in the smallest detail, those invincibility frames end at the precise moment Dedede can continue the infinite. His move does not stale, the timing changes ever so slightly, in time, I was able to continously infinite Luigi, even after I turned the speed back to it's default. I tested this on Mario and Samus as well. The timing just simply changes very vaguely. The throw doesn't stale at all.
In conclusion, another reason arises to why infinites are hard to achieve on those three characters, and that is an error in input. This is unavoidable and is on the game's end of mistakes, not the player. Sometime, under a cluster of button mashing or otherwise, the game would only read the guard input first before the attack, thus making the character put up a shield instead of grabbing. This affects the already sensitive timing of performing an infinite on Samus, Mario and Luigi.
Membership plox.