The remote entanglement of two atomic quantum memories through photonic interactions is accompanied by atomic momentum recoil. When the interactions occur at different times, such as from the random emission over the lifetime of the atomic excited state, the difference in recoil timing can expose ``which-path'' information and ultimately lead to decoherence. Time-bin encoded photonic qubits can be particularly sensitive to asynchronous recoil timing. In this paper we study the limits of entanglement fidelity in atomic systems due to recoil and other timing imbalances and show how these effects can be suppressed or even eliminated through proper experimental design.