We investigate the dependence of the complete system of 22 Lick indices on overall metallicity scaled from solar abundances, [M/H], from the solar value, 0.0, down to the extremely-metal-poor (XMP) value of -6.0, for late-type giant stars (MK luminosity class III, log(g)=2.0) of MK spectral class late-K to late-F (3750 < Teff < 6500 K) of the type that are detected as "fossils" of early galaxy formation in the Galactic halo and in extra-galactic structures. Our investigation is based on synthetic index values, I, derived from atmospheric models and synthetic spectra computed with PHOENIX in LTE and Non-LTE (NLTE), where the synthetic spectra have been convolved to the spectral resolution, R, of both IDS and SDSS (and LAMOST) spectroscopy. We identify nine indices, that we designate "Lick-XMP", that remain both detectable and significantly [M/H]-dependent down to [M/H] values of at least ~-5.0, and down to [M/H] ~ -6.0 in five cases, while also remaining well-behaved . For these nine, we study the dependence of I on NLTE effects, and on spectral resolution. For our LTE I values for spectra of SDSS resolution, we present the fitted polynomial coefficients, C_n, from multi-variate linear regression for I with terms up to third order in the independent variable pairs (Teff, [M/H]), and (V-K, [M/H]), and compare them to the fitted C_n values of Worthey et al. (1994) at IDS spectral resolution.