The two-stopper only arrived with the 747-400 which had the range to do it. We lived in Bahrain in the 70s and early 80s and the Far Eastern flights used to stop there for fuel and avoid the LHR curfew.
I first went to Australia in 1988. I flew in Garuda as it was a mere £800 as opposed to BA/Qantas who charged £1,300. The route was LHR-FRA-AUH-SIN-CGK-DPS-MEL-SYD!