The problem with big companies such as Google who have offices in Australia is that they just ignore your application or will direct you to the European recruiter.
Thank you for the info about Working Holiday, I will indeed check it out.
Google's jobs site provides the postal addresses of many of their local offices. I don't know about Australia but many of their addresses are there. Also, they ran Want Ads in the San Jose Mercury News - scads of them.
I expect this is because Google doesn't work through third-party recruiters. That would cost billions, maybe tens of billions in commissions.
in you cover letter, maybe in your own handwriting on the back of the envelope, point out that you really do want to live in Australia, and hope to do so by working for the likes of Google.
https://www.google.com/about/careers/search?jl=Sydney,Austra...
Disclaimer: I applied to work at Google Sydney, got the job, and was relocated. (From Melbourne, mind you, but there are people here from all over the globe.)
There are a lot of good tech companies in Australia! Good luck and let me know if you got any questions, I've been down here for almost 2 years on a sponsored working visa, it's lovely and not nearly as deadly as rumored :)