VH-HPL was on track from Perth to Rottnest Island, maintaining 2000 ft when VH-EAJ departed Perth for Singapore. The pilot of VH-EAJ had requested a clearance to enable the aircraft to initially track north along the coast, visually, at 2000 ft. VH-EAJ was cleared intiially at 3000 ft. When the aircraft reached 3000 ft the pilot advised that they "would like 2000 if its available .....3000 is just above cloud". VH-EAJ was then cleared to descend to 2500 ft which was the lowest assignable altitude to keep the aircraft 1000 ft above tha base of controlled airspace. At this time VH-EAJ was on radar vectors, heading 280 deg, which was keeping the aircraft to the south of VH-HPL but on a converging track. VH-EAJ was then asked to "report sighting a Britten Norman Islander (VH-HPL) in your two o'clock.....four miles maintaining 2000 ft.......". The crew of VH-EAJ were unable to sight VH-HPL. They were then instructed to climb to their planned cruising level of flight level 350. They were then asked again if they had the traffic sighted but reported "negative we're in cloud". They were then asked their present level and reported they were at 3100 ft. Separation between the two aircraft reduced to two miles with less than 1000 ft vertical separation.