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 φ(t). In accordance with previous studies, we find φ(t) to decay nonexponentially and follow a power-law φ(t)∼t−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<x<2 under conditions where diffusion is truly two-dimensional, while in phases where adatoms diffuse in a one-dimensional fashion along ideal rows of vacancies, we find a regime characterized by x<1. Also, changes in the qualitative behavior of x are closely related to phase boundaries and local ordering effects. Our studies suggest that φ(t) can be used to obtain information about the ordering of the system and about the nature of predominant interactions between adparticles. Our predictions can be tested experimentally by techniques such as scanning tunneling microscopy, in which φ(t) can be measured in terms of discrete adparticle displacements as shown in this work. Finally, our studies suggest that the decay of velocity correlations in collective diffusion follows, qualitatively, the same behavior as the decay of single-particle velocity correlations in tracer diffusion.