A new one to consider, NZ Airpoints.
Since 16 Nov 04, NZ has a "any seat can be an award seat" system. If you find a fare and have enough Airpoints Dollars to cover it (1 AD = 1$) then you can get the seat. For long haul there are also special rates (with limited availability).
For more details visit the NZ forum, or
www.airnewzealand.com.
PS the former restriction to certain countries has now been removed.