I assume that you are asking about the perspective from the US and the EU. The following is the US perspective, although I lived for many years in the EU (Germany) and about 50% of my research was based in Tasmania, so I have some familiarity with people holding PhDs from both places.
Since the question is about perception, the only good way to answer it would be by doing a survey of US/European researchers and ask questions about the relative value (however defined) of a PhD from 'anonymous university' in Australia. I don't know of such a survey.
The words "US PhD" covers a wide range. You have the ivies, and R1s, and on the other end you have what are essentially mail-order PhDs. And within the highly-ranked universities, you of course have different professors with their individual reputations. In my experience, Australian states and European countries have fewer (no?) universities printing mail order PhDs. By which I mean that if you come from a relatively unknown university in Australia or the EU, I'd assume it's a real PhD, while if you come from a relatively unknown university in the US, I'd check if the degree is real. So the following assumes that everything else is being equal, e.g. reputation of the university, professor/advisor, etc.
People with recent European or Australian PhDs tend to be on the shallow/narrow end of having background knowledge of the history of the field, as compared with US PhDs. The keyword here is "tend": the two bell curves have a lot of overlap. I acknowledge that this could be specific to my field, Biology, where it's impossible to cover the whole historical and technical aspects, so knowledge in one end comes at the expense of the other. If this matters when hiring, it depends on the opinion of those doing the hiring. But I think that this perception exists.
In my experience hiring, people with PhDs from the US tend to be more experienced teachers. This does not mean that US PhDs are better teachers, but that, at least in my field, the perception exists.
Another perceived difference, and this is based on complaints from PIs in the US when talking about non-US postdocs, is the holiday culture of Europeans. For example, I did a postdoc at a US lab (R1 institution) led by an European PI, who hired lots of European postdocs. These postdocs would pretty much work 3-4 days a week, not answer email during nights or weekends, make every US holiday a long weekend (e.g. come back to the lab on Wed after every holiday falling on a Mon), then take off a full month during Christmas and pretty much disappear during the summers. In my experience, Australian PhDs fall in between European and US attitudes towards holidays. I lived in Germany for many years, and certainly appreciated this aspect of European culture. But in terms of perception, which is the OP's question, I think that it's a real issue.
As others have pointed out, what will get you an academic job are your publication record, your history with grants, your teaching experience, and your letters of reference. So there's little use in worrying about how your PhD is perceived just because you come from an Australian university. But you asked about perception, and that's my perspective after 20+ years as a US-based academic.