We report a surprisingly long spin relaxation time of electrons in Mn-doped p-GaAs. The spin relaxation time scales with the optical pumping and increases from 12 ns in the dark to 160 ns upon saturation. This behavior is associated with the difference in spin relaxation rates of electrons precessing in the fluctuating fields of ionized or neutral Mn acceptors, respectively. For the latter the antiferromagnetic exchange interaction between a Mn ion and a bound hole results in a partial compensation of these fluctuating fields, leading to the enhanced spin memory.