UA flew LAX-AKL-MEL (842/843), LAX-SYD, and SFO-SYD for ages. Going to MEL via AKL is MISERABLE. That flight used to leave LAX around the same time as the SYD flight and get into AKL around 5AM. You would have to wake up, spend an hour and half on the ground in AKL with the airport basically shut down (albeit a very nice airport), then get back on the plane for the hop to MEL. It was awful. I much prefer going to MEL via SYD. As I recall they downgauged the LAX-AKL service (from a 744 to a 772) around the end of 2002/beginning of 2003 and then cancelled the service entirely around the middle of 2003 (at which time they added the SYD-MEL sector to continue MEL service).

As mentioned UA ran the LAX-MEL non-stop (847/848) for a while around the end of 2000 and beginning of 2001. When I flew it an FA told me that it was (at the time) the longest non-stop in the world, but that it was also seasonal because of weather. It was a weight restricted flight, I remember hearing a NW pilot explaining that she was trying to jumpseat on the flight but would have to wait and see where the flight weighed in to determine if they would let her on or not. I believe that QF operates LAX-MEL non-stop with today with the 744ER.