Angle-resolved photoemission was used to measure the Fermi contours of surface-localized states on the Mo(110) and W(110) surfaces with varying amounts of adsorbed lithium. In analogy with recent results for hydrogen adsorbed on the same surfaces, we find that the contours may have sufficient nesting to drive a surface phonon (Kohn) anomaly. The nesting vector along <()over bar>-->(H) over bar (parallel to the <()over bar> azimuth) on Mo(110) at monolayer coverage is measured to be 1.06 +/-0.05 Angstrom (-1), which is compared to recent phonon measurements by electron energy-loss spectra. We also report the variation of this nesting vector as a function of coverage, and show that a more complete understanding of the electron-phonon coupling on these surfaces might be obtained from coverage-dependent measurements of surface phonon dispersion relations. Finally, our results suggest there is even better nesting along the <()over bar>--> (S) over bar direction and that a more pronounced Kohn anomaly might be observed there.