Maybe I'm sending you in the wrong direction but if you go on
Google and search for 'registered training organisations' you can get the list of all of the approved training providers in OZ. Maybe it may help to contact them directly as opposed to registering with recruitment agencies.
Good luck. Hope you find something. The list is really comprhensive - I looked it up as I used to be an NVQ trainer.