I derive a mode-coupling theory for the velocity autocorrelation function, psi(t), in a fluid of randomly driven inelastic hard spheres far from equilibrium. With this, I confirm a conjecture from simulations that the velocity autocorrelation function decays algebraically, psi(t) ~ t^{-3/2}, if momentum is conserved. I show that the slow decay is due to the coupling to transverse currents.