On taxiing and after departure, the crew completed the required radio transmissions. They were advised to call Melbourne Control for an airways clearance prior to entering controlled airspace but were not advised of any conflicting traffic. When the crew requested clearance, Melbourne Control asked them if they were aware of an opposite direction aircraft that was leaving controlled airspace on descent to Ayers Rock. When the crew replied they were unaware of the traffic, Control gave details of the other aircraft. The descending Boeing 737 was sighted ahead and a left turn was commenced. The crew of the climbing aircraft estimated that the descending aircraft passed overhead with a vertical separation of about 1,000 ft. The climbing aircraft was then cleared to enter controlled airspace. Safety Action: As a result of several occurrences involving opposite direction traffic conflictions, a NOTAM was issued that prescribed a new air route and specified a `racetrack' route pattern between Alice Springs and Ayers Rock. This route system will be made permanent during the review process being conducted by the Civil Aviation Authority.