Is recommendation a must for getting PhD admission in Australia
The short answer is yes. You're not going to get PhD admission virtually anywhere in the world without letters of recommendation. 

But there's something more important: your approach is wrong. You should not start by contacting professors directly. First, find out if the university has a centralized PhD program (these centralized programs are very common in the US, for example). As far as I'm aware, Australian unviersities do not, but if they do then contacting professors individually is just inappropriate and a waste of time; you should apply to join those.

If they don't then you should find out if they're recruiting PhD students. They might have a webpage with a list of possible projects for example. If they do then you want to check those projects out and make sure you're interested before contacting them.

Here's an example of how to get a PhD position in astronomy at the Australian National University. After Googling for this, you should land at this webpage for the RSAA. You can see what topics are being studied there. You can also find a link to a list of potential projects, sortable by the level of study. Restricting the search to only PhD-level projects, the first result as of time of writing is this one on 3D modelling of nearby galaxies by Dr. Brent Groves, with a short description of what is involved. If you like the project, then you can email Dr. Brent Groves with your CV, motivation statements, thoughtful questions about the project (if any), and ask him if he's willing to supervise you. If you've read Dr. Brent Grove's work and have a suggestion for a potential project, you could write that too. If you just send your CV and "thesis" (what's this?) without any apparent knowledge on what Dr. Brent Groves is doing, he's likely to just ignore you.