The reflected entropy $S_R(A:B)$ of a density matrix $rho_{AB}$ is a bipartite correlation measure lower-bounded by the quantum mutual information $I(A:B)$. In holographic states satisfying the quantum extremal surface formula, where the reflected entropy is related to the area of the entanglement wedge cross-section, there is often an order-$N^2$ gap between $S_R$ and $I$. We provide an information-theoretic interpretation of this gap by observing that $S_R - I$ is related to the fidelity of a particular Markov recovery problem that is impossible in any state whose entanglement wedge cross-section has a nonempty boundary; for this reason, we call the quantity $S_R - I$ the Markov gap. We then prove that for time-symmetric states in pure AdS$_3$ gravity, the Markov gap is universally lower bounded by $log(2) ell_{text{AdS}}/2 G_N$ times the number of endpoints of the cross-section. We provide evidence that this lower bound continues to hold in the presence of bulk matter, and comment on how it might generalize above three bulk dimensions. Finally, we explore the Markov recovery problem controlling $S_R - I$ using fixed area states. This analysis involves deriving a formula for the quantum fidelity -- in fact, for all the sandwiched Renyi relative entropies -- between fixed area states with one versus two fixed areas, which may be of independent interest. We discuss, throughout the paper, connections to the general theory of multipartite entanglement in holography.