We study nuclear relaxation in the presence of localized electrons in a two-dimensional electron gas in a disordered delta-doped semiconductor heterostructure and show that this method can reliably probe their magnetic interactions and possible long-range order. In contrast, we argue that transport measurements, the commonly employed tool, may not sometimes distinguish between spatial disorder and long-range order. We illustrate the utility of using the nuclear relaxation method to detect long-range order by analyzing a recent proposal made on the basis of transport measurements, on the spontaneous formation of a two-dimensional Kondo lattice in a 2D electron gas in a heterostructure. © 2009 The American Physical Society.