In GaN:Mg, the MgGa acceptor is compensated extensively by the formation of nitrogen vacancies (VN) and Mg interstitials (Mgi). However, we show that such compensation can be overcome by forming two kinds of Mg-rich complexes: one that contains VN and the other that contains only MgGa and Mgi. Such complexing not only neutralizes VN and Mgi but also forms better complex acceptors that have lower formation energies and smaller hole localization energies than isolated MgGa. Our results help explain the different doping behaviors in samples grown by different methods.