9V-STT was en-route from Perth to Singapore and tracking via air routes B469 then R586 after Carnarvon, cruising at flight level (FL) 350. VH-EAL was also Perth for Singapore but tracking via air route G337 at FL350. The routes flown by the two aircraft are initially laterally separated but, because the cross-track tolerance changed as the aircraft proceeded north, it was necessary to apply separation to ensure that the standards were not infringed. This action was not completed by the air traffic controller responsible for the aircraft by the required point along the routes, and the standards were infringed. About 30 minutes prior to the incident there was a change of controller on the sector responsible for the aircraft. The controller commencing duty thought that he had confirmed that correct separation existed. The handing over controller believed the other controller had referred to two different aircraft when they discussed the adequacy of the separation during the handover. The controller assuming responsibility for the aircraft had recently returned from a period in the Perth Control Tower and may have forgotten, because of a lack of recent experience, that the cross-track tolerances of the two routes vary. The handing over controller was recently rated in the position and assumed that the more experienced controller was aware of the lack of separation between the routes. Safety Action: The Civil Aviation Authority is redesigning the route structure, and this should remove the potential for separation reductions in this area of airspace.