Thanks, whopity.
Emirates Flying School said they don't do JAA checks, but that was maybe just the switchboard guy who thought so.
I am only in Melbourne for about 16 hours, so I cannot travel outside Melbourne for the check. I talked to a local flying school, and they also mentioned Perth. Even Adelaide is about 400 miles away from Melbourne.
Regarding skill test vs. PC: In Denmark skill tests can only be made by CAA examiners, and the fees for the check alone is sky high now, probably amongst the most expensive in the world. A PC would only cost me the "normal" examiner, the rent of aircraft and landing fees. I don't think for practical reasons that the tests would be the same, as I have heard the PC can be done more or less in the circuit, where as the skill test is a full monty check, with all the extra planning and that.