VH-AJJ was climbing to Flight Level (FL) 370 (37,000 feet) whilst VH-WGJ was climbing to FL350 and the aircraft were under the procedural (non-radar) control of the Perth Sector 1 air traffic service controller. The aircraft were on reciprocal tracks and a vertical separation of 2000 feet was required at least 10 minutes before the aircraft passed. The climb profiles of the aircraft meant that the required separation would not be achieved by 10 minutes prior to passing. The controller did not recognise the potential confliction. Nine minutes prior to the aircraft passing, VH-AJJ requested an amended level of FL350 but was given FL330 because the controller assumed VH-WGJ was already at FL350. Seven minutes prior to passing, the controller ascertained that VH-WGJ was passing FL320. He then realised a conflict existed and instructed VH-WGJ to descend to FL310. VH-WGJ started its descent back to FL310 as VH-AJJ reached FL330 on the climb. The aircraft reached the standard vertical separation requirements approximately three minutes prior to passing. Although the controller was an experienced procedural sector controller he had not been involved in this type of control for about 12 months, and had only recently been re-categorised.