Not Australia, but I have MS Autoroute GB which does reasonable coverage of Western Europe as well. It is extremely slow if you leave the data on the CD. The good news is that one can load everything (abt 500 megabytes) onto the hard disk, at which point response times are good, even with a 450 MHz processor. In comparison, at least older versions of DeLorme Street Atlas for the USA work fine on a 120 MHz laptop with 32 megabytes of RAM reading map data directly from the CD. MS needs more efficient programmers. I don't think DeLorme has products outside the USA.
I'd suspect that Ozzie mapping from MS would be just as demanding as the GB version I have.
seacue