A partial attempt to address this issue is made by invoking the idea of quantum discord. The basic idea of quantum discord is the environment needn't be in a specific state prior to interacting with the system. All that is necessary is that it factorizes and there is no correlation.

Let's start with the simple example of a qubit, and an environment which is initially in a maximally mixed state, not a pure one. Assume the pointer states are $|0\rangle$ and $|1\rangle$, and it's the same no matter what state the environment is in, and that the pointer states are exact. This is only a toy model after all. Suppose $$|0\rangle\otimes|e\rangle \to |0\rangle \otimes U |e\rangle$$ and $$|1\rangle\otimes|e\rangle \to |1\rangle \otimes V |e\rangle$$ where U and V are unitary matrices acting upon the environment.

Now you might think, if the environment is in a maximally mixed state before interacting, it will still be maximally mixed after interacting, so how can there be decoherence? It's possible, however.

In block matrix form, an initial qubit state $\alpha|0\rangle + \beta |1\rangle$ transforms as $${1\over N}\begin{pmatrix}|\alpha|^2 I & \alpha\beta^* I\\\alpha^*\beta I & |\beta|^2 I\end{pmatrix} \to {1\over N}\begin{pmatrix}|\alpha|^2 I & \alpha\beta^* UV^{-1}\\\alpha^*\beta VU^{-1} & |\beta|^2 I\end{pmatrix}$$ for the density matrix where N is the dimensionality of the state space of the environment. Taking the partial trace over the environment, we get $$\begin{pmatrix}|\alpha|^2 & \alpha\beta^* Tr[UV^{-1}]/N\\ \alpha^*\beta Tr[VU^{-1}]/N& |\beta|^2\end{pmatrix}$$. For generic unitary matrices, the two traces divided by N scales as $1/\sqrt{N}$ assuming some very mild statistical distribution properties.

How can a maximally mixed environment record any information about the qubit? It can't, but it can still decohere the qubit!

Physically, consider a molecule decohered by light shining on it and scattering off it. If most of the photons are coming from only one direction, e.g. sunlight only coming from the direction of the sun at a certain spectral distribution, and the photons are scattered off in different directions at a different frequency spectrum, we can see how the scattered photon carry off information about the location of the molecule, its energy level prior to the scattering, and the difference between its energy levels (assuming its an inelastic scattering).

However, place the molecule in a closed box filled with blackbody radiation in thermal equilibrium. The blackbody radiation can still decohere the position of the molecule and its energy levels even though the blackbody photons can't carry any information about the molecule!

The OP's question is about a different case though, where the different environmental states have different pointer states. This has also been covered by Zurek. Assume a dilute gas of environmental particles scatter off the molecule from different directions and velocities. The pointer states depend upon the direction and velocity of the scattering probe, as can be shown by an examination of the S-matrix. What happens in this case after a number of collisions is thermalization, not decoherence in the form of dephasing in a specific pointer state basis.

That's still not what the OP's question is about. The previous paragraph is for an environment in a thermal state. The OP's question is about an environment in a superposition which is nonthermal. There is also only one interaction, and not multiple scatterings. I'm afraid the question is still open as it stands.