Transport properties of a hard-sphere colloidal fluid are investigated by Brownian dynamics simulations. We implement a novel algorithm for the time-dependent velocity-autocorrelation function (VACF) essentially eliminating the noise of the bare random motion. The measured VACF reveals persistent anticorrelations manifested by a negative algebraic power-law tail $t^{-5/2}$ at all densities. At small packing fractions the simulations fully agree with the analytic low-density prediction, yet the amplitude of the tail becomes dramatically suppressed as the packing fraction is increased. The mode-coupling theory of the glass transition provides a qualitative explanation for the strong variation in terms of the static compressibility as well as the slowing down of the structural relaxation.