We investigate the low-temperature behavior of paramagnetic Kondo lattices upon random depletion of the local f moments by using strong-coupling arguments and solving SU (N) saddle-point equations on large lattices. For a large range of intermediate doping levels, between the coherent Fermi-liquid of the dense lattice and the single-impurity Fermi liquid of the dilute limit, we find strongly inhomogeneous states that exhibit distinct non-Fermi-liquid characteristics. The interplay of dopant disorder and strong interactions leads to rare weakly screened moments which dominate the bulk susceptibility. Our results are relevant to compounds like Cex La1-x Co In5 and Cex La1-x Pb3.