Chemical modelling of AGB outflows is typically focused on either non-thermodynamic equilibrium chemistry in the inner region or photon-driven chemistry in the outer region. We include, for the first time, a comprehensive dust-gas chemistry in our AGB outflow chemical kinetics model, including both dust-gas interactions and grain-surface chemistry. The dust is assumed to have formed in the inner region, and follows an interstellar-like dust-size distribution. Using radiative transfer modelling, we obtain dust temperature profiles for different dust types in an O-rich and a C-rich outflow. We calculate a grid of models, sampling different outflow densities, drift velocities between the dust and gas, and dust types. Dust-gas chemistry can significantly affect the gas-phase composition, depleting parent and daughter species and increasing the abundance of certain daughter species via grain-surface formation followed by desorption/sputtering. Its influence depends on four factors: outflow density, dust temperature, initial composition, and drift velocity. The largest effects are for higher density outflows with cold dust and O-rich parent species, as these species generally have a larger binding energy. At drift velocities larger than $\sim 10$ km s$^{-1}$, ice mantles undergo sputtering; however, they are not fully destroyed. Models with dust-gas chemistry can better reproduce the observed depletion of species in O-rich outflows. When including colder dust in the C-rich outflows and adjusting the binding energy of CS, the depletion in C-rich outflows is also better reproduced. To best interpret high-resolution molecular line observations from AGB outflows, dust-gas interactions are needed in chemical kinetics models.