South Pacific (includes AU) to Europe in coach should be 50,000 one way, as per the nwa.com SkyMiles award charts (before Dullta took them down - can't actually tell the customers what their SkyMiles are worth! though really no reason not to, many of the award levels are not that uncompetitive, only some are). Oddly though, there is nothing listed for business class.. not quite sure what does that mean.

It should be possible though certainly to book it on MH via KUL or KE via ICN. Just keep calling and get a more skilled and helpful agent. If no such luck, ask them to transfer you to IRRRES, which are the expert agents who should be able to make this (simple, should be bookable online, as it was on nwa.com) happen for you.

Make sure to ask them to piece it together by segment, not the whole trip.
I.e. first get SYD-ICN. If available and confirmed, then add ICN-LHR. If both set and on a PNR, then they can forward it to IRRRES for ticketing/manual repricing. The key is to first get a PNR assembled, and to do so always best if you don't try to get the agents to think and just tell them what to do, which specific flights you want and if available put it all on PNR. Worry about pricing it out and ticketing later, once all the flights you want are assembled and confirmed.

The stone age DumbMatic is probably not programmed to price this properly automatically (it often can't even price simple US domestic flights properly if it involves AS for one segment and DL for another segment, and the DL segment is medium or high and not low), so you will need IRRRES or IXXRES to force it through and manually reprice it. Not sure if they can still override it and use the WP (WorldPerks) instead of SM (SkyMiles) pricing in the Fare Calculation, as I know could be still done a few months ago and was the one way around such difficult (though should not be) cases. May be worth to ask, can they do it under WP vs SM pricing under Fare Calculation to make it happen.