We consider adatom dynamics and diffusion in a lattice-gas model of the O/W(110) system under conditions where the adatom interaction effects are important. In particular, we study the behavior of the tracer and collective diffusion coefficients as a function of temperature when crossing over from the high-temperature disordered phase to a low-temperature symmetry broken phase. To this end, we utilize a combined analytical and numerical approach based on the recently developed dynamical mean field theory (DMF) in addition to conventional Monte Carlo simulations. In the case studied here, the origin of the strong temperature dependence of the effective activation barrier EDA close to an order-disorder transition, i.e., the non-Arrhenius behavior of the diffusion coefficients, can be traced back to that of the average microscopic jump rate Γ appearing within the DMF. This is in contrast to the usual assumption that thermodynamics controls diffusion near phase transitions. The behavior of Γ, in turn, is found to arise predominantly from critical effects in the short-time behavior of the waiting-time distribution of single-particle jumps, W(t), which is an experimentally accessible quantity. The long-time decay of W(t) is then used to define another effective barrier EWA, which shows no anomalous effects near the transition.