One way around this is to relax the definition of the second law to be something like "almost always": the set of states with higher entropy are incredibly unlikely. And when you compute the recurrence time, it's astoundingly large; like trillions upon trillions of ages of the universe.
Cosmologically, there is some escape in that the expansion of the universe breaks the assumption of finite accessible phase space, but there is an underlying difficulty of what it means for the universe to be truly infinite or divergent in size. Not just really big, but truly infinite: where did it all come from?
My personal take is that the second law is about "macroscopic" experiments. You are given a box and you can only do things like push the side of box or put it on a hot stove or in a magnetic field or whatever, and the laws are about what you can or cannot do with those operations. The microscopic system might decide to do something incredibly unlikely, but you can't control or even anticipate it, and that is just the extremely long tail of the probability distribution that is a thermodynamic state.
I don't claim my view is rigorous; people like Boltzmann and Ehrenfest were much smarter than me and struggled with what irreversibilty means, and you can kind of go crazy worrying about this (likewise with the 'measurement problem' of quantum mechanics). In the end, whether a situation can be mapped to the exact axioms of a model like QM or thermodynamics is very tricky and perhaps unknowable.