  The maximal amount of information which is reliably transmitted over two uses
of general Pauli channels with memory is proven to be achieved by maximally
entangled states beyond some memory threshold. In particular, this proves a
conjecture on the depolarizing channel by Macchiavello and Palma [Phys. Rev. A
{\bf 65}, 050301(R) (2002)]. Below the memory threshold, for arbitrary Pauli
channels, the two-use classical capacity is only achieved by a particular type
of product states.
