You always hear theoreticians proudly proclaim the AdS/CFT correspondence implies time evolution for evaporating black holes is unitary. But if you examine the argument carefully, you find AdS black holes can't completely radiate away because the outgoing Hawking radiation always fall back into the black hole in an asymptotically anti de Sitter geometry. To get a black hole which completely evaporates away, we need a zero or positive cosmological constant.
For the information loss paradox, it's completely irrelevant that the radiation may get reflected from the AdS boundary. What is important is that the information is not being lost while the radiation is leaving the region around the black hole horizon.
If the causal arguments based on classical general relativity were valid, the information about the state would already disappear when the radiation leaves the black hole. By causality, one can't imprint the information from the black hole interior to the exterior region (i.e. to the radiation). This failure to preserve the information would violate unitarity already at the moment when the radiation is emitted. However, unitarity holds in AdS/CFT at all times which proves that the classical argument based on causality is circumvented in quantum gravity.
Much more generally, it is not true that the negative cosmological constant makes any difference to the paradox. In particular, it is not true that all the radiation has to return to the same black hole. If the AdS curvature radius is large enough, the AdS space may host millions of other black holes and/or stars aside from the black hole whose information we analyze (it's a large universe just like ours!), and the radiation may get reflected to those other objects.
Even more generally, physics in an AdS space with a low enough curvature is clearly locally indistinguishable from physics in flat space. Assuming nonlocalities at most at the distance scale of the black hole radius, it's clear that if the AdS radius is much longer than the black hole radius, physics can't be qualitatively affected by the nonzero AdS curvature.