Is decoherence even possible in anti de Sitter space? The spatial conformal boundary acts as a repulsive wall, thus turning anti de Sitter space into an eternally closed quantum system. Superpositions remain superpositions and can never decohere. A closed system eventually thermalizes and undergoes Poincare recurrences. Whatever the dual is to an interacting conformal field theory, is it really a theory of quantum gravity, or does it only look like one superficially?
Your question is not about AdS at all, it is about a closed quantum system with a finite number of degrees of freedom.
If you examine the space-time near a finite area quantum black hole, you will see an approximate AdS space. For this reason, my original answer included AdS spaces in the list of finite systems, although this is completely false for what people would call a normal classical AdS space. Thse spaces are unbounded and make open systems. The near horizon extremal black hole is presumably sitting in an infinite spacetime, so it is also an open quantum system. So it is best to reformulate the question for the domain you intended:
How can you have irreversible decoherence in a closed quantum system with a finite number of degrees of freedom?
The same question can be formulated to a certain extent in a closed classical system, where Poincare recurrences still occur. How can you reconcile poincare recurrence with irreversible information gain by an observer?
I think the many-worlds point of view is most useful for understanding this. If you have a closed quantum system that contains an observer, it is the observer's gain in information that determines which relative branch of the wavefunction becomes the real one for this observer, a branch selection from the decohered branches which occurs outside the theory. The branches are still effectively dechered so long as the arrow of time is still forward, because the wavefunction is spreading out into new regions of the enormous phase space. It is reasonable to think that the system will need to thermalize and destroy all the observers long before the recurrence makes the entropy decrease to the initial value.
This observer can only exist while there is an arrow of time, so there is no real paradox. You can have effective decoherence and measurements for the thermodynamic arrow-of-time stage. The same is true in classical closed system, the observer will have to dissociate and reform in order for the system to have a poincare recurrence.
But perhaps you meant this as a counterexample to the claim that irreversible decoherence can occur in pure closed-system quantum mechanics. In this case, I agree that it is obvious that the closed system cannot really decohere irreversibly, since it will eventually recohere to close to its initial state.
Decoherence is more than anything a matter of what you define to be the "environment". The environment is supposed to be external to the system of interest and entangling interaction with it produces decoherence. If the environment in question is a part of the adS space then the subsystem can certainly decohere. If what you are asking is whether the space as a whole can decohere when it's isolated from its environment then the answer must by definition be no.