We bring forth a consistent theory for the electron-mediated vibrational intermode coupling that clarifies the microscopic mechanism behind the vibrational relaxation of adsorbates on metal surfaces. Our analysis points out the inability of state-of-the-art nonadiabatic theories to quantitatively reproduce the experimental linewidth of the CO internal stretch mode on Cu(100) and it emphasizes the crucial role of the electron-mediated phonon-phonon coupling in this regard. The results demonstrate a strong electron-mediated coupling between the internal stretch and low-energy CO modes, but also a significant role of surface motion. Our nonadiabatic theory is also able to explain the temperature dependence of the internal stretch phonon linewidth, thus far considered a sign of the direct anharmonic coupling.