I have heard complaints about that company even here, in the UK -- yours is not the first -- mostly from online Aussie friends. You should take some kind of action, through legal channels, of course. Some people will not change unless you teach them a lesson.
For example, you can state your case at various places to bring the company bad publicity. As long as you are factual, it is not slander. Make sure the company knows what you are doing. In all likelihood, if they know they do not have a case against you, they will try to please you to get you to shut up.
In your correspondence to them, keep your prose factual and not personal. Refrain from comments like "You suck" (not that I am saying you say that) because it achieves no objective and only reflects on you. Make it look like you are keeping meticulous records in the event of a legal case.
Of course, there are usually fair business practice oversight commitees, although I am unsure about how the legal system is set up in Australia.
You could also try setting up a counter-website, like www.ihatetelstra.com.au, although you should be prepared for legal flak