Since everybody seems to need the kid who cries that the emperor has no clothes, I am more than happy to make the same statement in an answer: the question posed by the black hole complementarity paradox is unphysical.
Information is always lost in any physical systems. Thermodynamics is about nothing else than information loss. Whether it's melting ice cubes losing their shape, a heart on the foam of a cup of latte disappearing by stirring or the initial conditions in a gravitating n-body problem getting tangled to absurdity - we can never get the full information about the past back.
Let me repeat this: that is normal and one can easily deduce it from special relativity: outgoing radiation is leaving a localized system at the speed of light, which, as we hopefully all accept, can not be caught up with. Once thermal radiation is gone, it's gone, and it takes part of the system state with it. Even if we could do the inverse reconstruction of the dynamic (which, as we know from classical mechanics, is not even possible for any but a handful of trivial Hamiltonian systems), we would already be lacking the necessary ingredients for this calculation: the lost heat has destroyed any chance of a full reversal.
Why some theoreticians of otherwise enormous intellect have taken offense with the normal modus operandi of nature is a real mystery, which I admit. The suggestion that black holes are the only information conserving devices in the universe is, on the other hand, very strange and I do not see a single shred of physical motivation for it, let alone any chance of testing this claim. And with that alone the question disappears, by definition, from the pages of science.