Spin echo experiments have been able to reverse the motions of all the molecules in a gas in statistical mechanics in the manner of Loschmidt. The Fermi-Ulam-Pasta model has solutions with a single mode dispersing, only to recohere after quite some time has elapsed. Can the same thing happen for decoherence? What are the conditions fyor decoherence to be irreversible?
An article you might be interested in: http://www.physics.arizona.edu/~cronin/Research/Lab/some%20decoherence%20refs/RBH97.pdf
Decoherence in a quantum mechanical system appears because the phase information is lost. If it were recorded/known then, as in your first example, one could reverse it. The answer for me seems to be complexity.
In some sense there exists a single quantum mechanical state function of the universe. To record it one would need oogleplexes of numbers and functions.
In my opinion, decoherence serves the same function that the transition from quantum statistical mechanics to thermodynamics does: it describes measurable experimentally quantities for the system under observation. If we knew all the parameters of the statistical ensemble we would get the same answers, but thermodynamics reduces the complexity.
Similarly working with a density matrix, the complexity of the quantum mechanical system is reduced to measurable quantities. So it is the number of parameters that have to be reversed that will decide whether decoherence is reversible or irreversible, and this will be time dependent as tools develop. Who would have thought that thousands of Feynman diagrams could be calculated as they are now doing for the needs of LHC experiments.