It's probably not as deep a paradox as Verin thought. She was explaining things as if all those worlds were "real" and what happened in one of them could influence the "real world". In fact it's most likely just reflections. The Wheel is not programmed to project what might happen beyond the moment of Shai'tan's victory. He is foreign to the Pattern. A victory of Shai'tan in the "Mirror Worlds" doesn't compute, no more than Viewings and Foretelling could tell if Shai'tan would win... those post TG were all projections of what could happen if Shai'tan lost. Shai'tan won in several Mirror Worlds, but that would never free him. It would have to happen in the real world for this to be reflected everywhere.. for as long as the Pattern lasts after that anyway.

The more interesting paradox (which shed some interesting light on a few things happening in the series, notably the fact Shai'tan does not appear to learn much or have memories of past confrontations to share with his "Champion" Moridin, to his great frustration) was this: outside the Pattern, in the "prison", time doesn't exist. Rand stepped outside time to confront Shai'tan. This strongly suggests that what appeared to Rand to be a unique confrontation, from Shai'tan's perspective was rather an infinitely multi-dimensional single confrontation. To the DO, all the LB from the first to the last (if there is such a final one planned) is one moment in an infinity of variants all happening in that single moment. And he lost. For good. He lost all the Battles before, and he lost all the ones from the future too as otherwise the past in which the story's third Age is set would have been undone even if Rand won...

Of course Ages will past and the world will forget it's already won that Battle.

The circularity of time in Creation means an infinity of confrontations happen through time... within the Pattern. For the DO outside it's all one battle outside time and space. It's much like the Bore which has a location in the physical world, a kind of manifestation of what it really is, because the physical rules of Creation forced things to exist in space and time, but that was actually a global weakness that's everywhere and nowhere because what it touches on is a dimension with neither space nor time.