The opportunity costs of doctors' time is higher than that of most of their patients, so it makes sense that there's typically a small backlog of patients in the waiting room. If somebody finishes early, the next in line jumps in and the doctor isn't left waiting around. Because of our willingness to wait around a bit, we all wind up paying a bit less for the doctoring services.
That's enough to explain short queues in the waiting room. But it isn't enough to explain half-hour waits. I'd wondered why the appointment scheduling software doctors use doesn't automatically send out update notifications to patients via SMS or email when backlogs hit the 20-minute mark; @GraemeEdgeler figured the cost of the system could never be recouped by most doctors.
That might be true in New Zealand, and especially for services provided under contract to the public health system. But the system is up and running in the States: MedWaitTime charges doctors $50/month, or $300/month for a full medical facility, for patient updating services. There's an iPhone app for patients. The doctor's secretary spends 30 seconds updating the doctor's status from Green to Yellow (moderate wait) or Red (long wait). Patients check the iPhone app before heading in. It's apparently not yet integrated directly into the doctors' appointment scheduling software, but I really can't see how that's all that hard; it's surprising that the folks who make the appointment and patient management software haven't already integrated in this kind of feature. The gains to patients avoiding long queues has to exceed $300/month for even a single doctor, never mind a practice.
It'll likely come to New Zealand. Eventually. After it's pervasive in the American system and enough ex-pats complain about not having it here.