On descent to Ayers Rock the pilot of VH-NJC contacted Adelaide Flight Service who advised that there was no other known conflicting instrument flight rules traffic. When approximately 37km from Ayers Rock, and approaching an altitude of 7,100 ft, the pilot made a broadcast on the Ayers Rock advisory frequency advising other aircraft in the area of his position. A reply was received from a visual flight rules aircraft reporting that it had departed Ayers Rock, was on a reciprocal heading, and also 37km from Ayers Rock, but at an altitude of 7,500 ft. The pilot stated that all mandatory radio calls had been made on departure. Both aircraft missed each other's calls as they were on different radio frequencies at the time the calls were made. Neither pilot saw the other aircraft.