We show that for particles performing Brownian motion in a frozen array of scatterers long-time correlations emerge in the mean-square displacement. Defining the velocity autocorrelation function (VACF) via the second time-derivative of the mean-square displacement, power-law tails govern the long-time dynamics similar to the case of ballistic motion. The physical origin of the persistent memory is due to repeated encounters with the same obstacle which occurs naturally in Brownian dynamics without involving other scattering centers. This observation suggests that in this case the VACF exhibits these anomalies already at first order in the scattering density. Here we provide an analytic solution for the dynamics of a tracer for a dilute planar Lorentz gas and compare our results to computer simulations. Our result support the idea that quenched disorder provides a generic mechanism for persistent correlations irrespective of the microdynamics of the tracer particle