We provide evidence that gallium purity is the primary impediment to attainment of ultra-high mobility in a two-dimensional electron gas (2DEG) in AlGaAs/GaAs heterostructures grown by molecular beam epitaxy (MBE). The purity of gallium can be enhanced dramatically by in-situ high temperature outgassing within an operating MBE. Based on analysis of data from an initial growth campaign in a new MBE system and modifications employed for a 2nd growth campaign, we have produced 2DEGs with low temperature mobility in excess of 35x10^6cm2/Vs at density n=3.0x10^11/cm2 and mobility 18x10^6cm2/Vs at n=1.1x1011/cm2. Our 2nd campaign data indicate that gallium purity remains the factor currently limiting mobility <40x10^6cm2/Vs. We describe strategies to overcome this limitation.