I find adioso.com interesting. I've not booked using it so far but have used it to check costings and flights. It provides rapid and easy access to information that others don't.
It has a (somewhat) natural language search engine (or a more conventional one can be used) and provides graphs of prices across date ranges. It highlights the cheapest flight in the date range selected both graphically and numerically. In the NZ-Asia region JetStar seems to feature a lot.
You can ask it questions like "AKL to CAN early October". I just had a look and they have made the search somewhat more formal with eg from and to boxes, but it is still quick and easy to use.
Probably not of interest, but within China I have made extensive use of http://ticket.9588.com/ with good results. They list all available internal airlines and allow you to see discount rates and number of seats at that rate for all future dates. Discounts of up to 70% AFAIR are available in some cases for early enough bookings.