- You may not have the appropriate visa
- You don't live in the country
- You aren't talented enough to overcome 1. and 2.
You may not have the appropriate Australian visa
I have all required documentation to work and live in Australia
Many foreign employers will hesitate providing full-time salaried employment to immigrants and only hire on contract basis or on the condition that the visa stays valid. Even if you have the visa now, the visa may not be appropriate for the position (many visas are only valid for certain types of employment), and/or renewal may be denied. The job description is sometimes required to match the type of employment for the visa under risk of the visa being revoked.
Most companies do not employ immigrants, and are not familiar with rules or regulations involving their hire. This means that there is an added hurdle/headache involved with bring you in to the company. Even if you tell a recruiter/employer that you have the appropriate documentation, they may not have the ability to judge if that is correct, and the responsibility for due diligence is on their part.
Whenever applying for a position in country where you do not have citizenship (and therefore require working permission), it is in your best interest to be incredibly clear about what your working permission is to minimize the effort required on the part of the employer to check.
You don't live in the Country
Even if you do have a visa, you will have to immigrate after accepting any offer. This could mean added cost or reduced availability while you open a bank account, find an apartment, get a phone, sign up for internet, etc.
Furthermore, there is no guarantee that you will actually like living in Australia. Even coming from another English-speaking country, there will be Culture Shock which may make you quit suddenly, or otherwise negatively impact your attention to your job and your relationship with your coworkers. The first time an Australian calls you a Seppo you may react with shock and horror at the uncouth nature of the Australians and board the first flight back from home.
You aren't talented enough to overcome 1. and 2.
So there's added effort due to being an immigrant who requires working permission.
There is added risk and cost from you not living in the country.
These are two (very huge and certain) demerits to hiring you over an equally qualified citizen. Unless you have merits that dramatically overwhelm those two risks, there is very little reason that they should hire you. Chances are that nothing in your resume or cover letter gave them incentive to put in the effort to overcome those two hurdles.
If you were a company/recruiting agency, what would you do?
You would sum this up as 'lack of local experience' or something of the sort.
In reality, they probably expect you to read through the lines. You aren't a good fit. That is an easy excuse. And despite having interviewed with them, you clearly don't feel comfortable asking them what they meant by lack of local experience, otherwise you wouldn't be asking about it here. I have met people who have worked in Australia from Japan, South Africa, Australia, and the US, so it certainly isn't impossible, they either had the skills to overcome the lack of residency/visa restrictions, or they moved there first on a working holiday or student visa and were able to apply locally.
It is incredibly difficult to apply for work from outside of the country you want to work in. The best ways to get to another country are to be hired by a company in your home country with an office (and opening) in the country you want to go to, and be transferred, or to take advantage of any programs in the target country that are specifically trying to recruit people from your country (this often happens with high-skill professions and/or cultural exchanges).
Barring those, you can always save enough money to live for 3-6 months and find a job after moving there (assuming your visa allows it).