Using resonant inelastic x-ray scattering (RIXS) at the Cu L-absorption edge, we have observed intense, dispersive spin excitations in highly overdoped Tl2Ba2CuO6+delta (superconducting T-c = 6 K), a model compound whose normal-state charge transport and thermodynamic properties have been shown to exhibit canonical Fermi-liquid behavior. Complementary RIXS experiments on slightly overdoped Tl2Ba2CuO6+delta (T-c = 89 K) and on Y1-xCaxBa2Cu3O6+delta compounds spanning a wide range of doping levels indicate that these excitations exhibit energies and energy-integrated spectral weights closely similar to those of antiferromagnetic magnons in undoped cuprates, indicating the persistence of substantial antiferromagnetic spin correlations over a wide doping range. The surprising coexistence of such correlations with Fermi-liquid-like charge excitations in highly overdoped cuprates poses a challenge to current theoretical models of correlated-electron metals.