We study the diffusive dynamics of adparticles in two model systems with strong interactions by considering the decay of the single-particle velocity correlation function phi (t). In accordance with previous studies, we find phi (t) to decay nonexponentially and follow a power-law phi (t)similar tot(-x) at intermediate times t, while at long times there is a crossover to an exponential decay. We characterize the behavior of the decay exponent x in detail in various ordered phases and in the vicinity of phase boundaries. We find that within the disordered phase, the behavior of x can be rationalized in terms of interaction effects. Namely, x is typically larger than two in cases where repulsive adparticle-adparticle interactions dominate, while attractive interactions lead to x <2. In ordered phases, our results suggest that the behavior of x is mainly governed by ordering effects that determine the local structure in which adatoms diffuse. Then the decay is characterized by 1