Hi there,
Just want to say i'm not some kind of broadband expert, so i can only give what information i've read or experienced.
The stop/starting i'd wager is packet loss, its worse than high ping as you said.
Interleaving (as you may know) is actually designed as error correction, so if you do get packet loss on your line, you won't notice it as much. Though its hard to say if its your phoneline causing it, or orcon. Im going to guess the latter though. Have you always got packetloss since getting interleaving turned off?

Your modem should be fine, im running a dynalink RTA1025w, but that shouldnt be causing the problem unless its faulty. If you could post the line stats from the Status > ADSL Line page in the web config, that might help.

Onto ISP's. I should add that Traffic management is not bad, in fact its necessary for games not to lag, otherwise people torrenting etc would take all the bandwidth. Its how they go about the management though that can completely change how reliable the service is.

As for Telstraclear, their huge customer base seems to make their phone support absolutely terrible. However we've had no problems with PDQ MAX/MAX, pings have been nice and low, and peak speeds haven't crawled like apparently happens on other ISPs.
This does come at a cost though, its not cheap compared to the alternatives, especially because data is purchased in blocks, so if you use 21gb, you pay for the full 30gb.

Other good ISP's are Xnet, Snap, and Slingshot, just from reading peoples experiences with them.
Xnet did have major issues with a sudden increase in customers, which caused problems which have now apparently been fixed. However some still report slowdowns at peak, but only a few, and it would seem peoples pings are now stable. On the upside for Xnet, you have no contract, no tolls required (but you can choose to use them), and free data to gameplanet, recoil and a couple of other sites.
Snap is based out of Christchurch, which might not help your Hamilton > Auckland pings, but apparently they are going to add routing through Auckland soon. They seem to have the best customer service of any, and reliable pings/speeds. Personally i'd choose them straight away if they went through auckland.
Slingshot is another big ISP, but the ops manager is a gamer, and so manages traffic pretty well for games. Pings seem to be reported as low, but peak speeds get slow for some, but most seem to find them good. On the upside is Data banking, where your data carries over to the next month, and free unlimited offpeak during the night, which helps keep the torrenters scheduling overnight.

That concludes my huge wall of text. Hope it helps.