Strongly Inhomogeneous Phases and Non-Fermi Liquid Behavior in Randomly Depleted Kondo Lattices