We show the existence of intrinsic localized spins in mesoscopic high-mobility GaAs/AlGaAs heterostructures. Non-equilibrium transport spectroscopy reveals a quasi-regular distribution of the spins, and indicates that the spins interact indirectly via the conduction electrons. The interaction between spins manifests in characteristic zero-bias anomaly near the Fermi energy, and indicates gate voltage-controllable magnetic phases in high-mobility heterostructures. To address this issue further, we have also designed electrostatically tunable Hall devices, that allow a probing of Hall characteristics at the active region of the mesoscopic devices. We show that the zero field Hall coefficient has an anomalous contribution, which can be attributed to scattering by the localized spins. The anomalous contribution can be destroyed by an increase in temperature, source drain bias, or field range.