p-doping of GaN is not impossible - you can take the Blu-ray as evidence.
However, you are right that it is difficult, and the efficiency is poor. The best (or least bad) dopant for making p-type GaN, at least so far, is Mg. The key problem is that no real shallow acceptors have been found in GaN. Even Mg (on Ga site) is a deep acceptor in the sense that the hole localizes on it rather strongly, and the state can not be viewed as an effective-mass-kind-of state as in the case of shallow levels. The ionization energy is, however, sufficiently low (about 250 meV) to produce some free holes if sufficient concentration of Mg is introduced in GaN. You can have a look at for example [Lany and Zunger, APL 96, 142114 (2010)] and related papers for further discussion about the physics of acceptors in GaN.
Another, more practical issue is that acceptor impurities, in particular Mg, are efficiently passivated primarily by hydrogen (that is typically incorporated during synthesis in fairly high concentration in GaN), and also by nitrogen vacancies (that are easily formed during growth when the Fermi level is low). Various post-growth annealing routines are applied with the aim to remove the passivation.
I really agree with the remarks of Filip Tuomisto. A review of the discussed topic can be found in my recently published book "Basic Properties of III-V Devices-Understanding Trapping Phenomena", kassel university press GmbH, 2014. I hope I could help you though your question is not the newest!