No maybe about Navman - it does have Australian maps. However, it is my understanding that you cannot buy the software (SmartST) on its own - it only comes bundled with their hardware.
I have a Navman PiN. The maps are basically all the UDB directories for Australia, so has very good detail for all the capital cities and a large number of country towns. Haven't had a chance to go much into rural areas yet, so not really sure how good that coverage is, a quick look around on the screen indicates to me that it really only provides major road information.
DiscoverAus Streets & Destinations from Magellan (I also have a Magellan Meridian) appears to have a lot more detail for rural areas (rivers, 4WD tracks, etc), but doesn't have things such as auto-routing, etc.
The Navman software makes use of POI data from Sensis & Whereis, so provides a pretty comprehensive database, although sometimes the software itself makes it a bit difficult to find what you are after (why can't we just have a free-text search???).
Of course, with any package there is the age of the maps to consider. I have found that the Navman maps have stuff that is reasonably recent (i.e. about a year ago), but also has certain items that are about 4 or 5 years out of date. Plus the odd error in the map data itself :? .
I have had a play around with a couple of packages that allow you to download your own maps, but of course you lose a lot of the avanced capabilities such as auto-routing... I will probably invest in one of these as they are reasonably priced (why pay for maps you may never use?). I figure that when I go 4WD, I can make up my own detail maps for the areas I will be going into, since auto-routing is not really a requirement.
Destinator mentions support for Australian maps from Mapinfo. How good they are, or how good the software is, I can't comment as I haven't tried it.
Cheers,
Mike.