Infrared (IR) laser spectroscopy is used to probe the rotational and vibrational dynamics of the (HCN)(m)-M-n (M = K, Ca, Sr) complexes, either solvated within or bound to the Surface of helium nanodroplets. The IR spectra of the (HCN)(m)-K (m = 1-3), HCN-Sr, and HCN-Ca complexes have the signature of a surface species, similar to the previously reported spectra of HCN-M (M = Na, K, Rb, Cs) [Douberly, G. E.; Miller, R. E. J. Phys. Chem. A 2007, 111, 7292.]. A second hand in the HCN-Ca spectrum is assigned to a solvated complex. The relative intesities of the two HCN-Ca bands are droplet size dependent, with the solvated species being favored in larger droplets. IR-IR double resonance spectroscopy is used to probe the interconversion of the two distinct HCN-Ca populations. While only a surface-bound HCN-Sr species is initially produced, CH stretch vibrational excitation results in a population transfer to it solvated state. Complexes containing multiple HCN molecules and one Sr atom are surface-bound, while the nu(1) (HCN)(2)Ca spectrum has both the solvated and surface-bound signatures. All HCN-(Ca,Sr)(n) (n >= 2) complexes are solvated following cluster formation in the droplet. Density-functional calculations of helium nanodroplets interacting with the HCN-M show surface binding for M = Na with a binding energy of 95 cm(-1). The calculations predict a fully solvated complex for M = Ca. For M = Sr, a 2.2 cm(-1) barrier is predicted between nearly isoenergetic surface binding and solvated states.