Yes Tornado's do exist in Australia, they're just not as big as those in the US so get labelled 'mini-tornadoes'.
I recall seeing an excellent report on possibly the largest recorded tornado in Australia(300M wide) on either Rob McNaught's or Gordon Garradd's website.
* Rob McNaught..
here's the link
I have seen one descend maybe 1/4 way down from a cloud but not touch down. There was a similar one to that I saw shown on the news here a few years ago, as well as a pretty speccy 'water spout'.
I also live in what has been dubbed Tornado Alley south of Perth.
I consider a waterspout to be a tornado, it's just that it occur's over water instead of land.
The link to the news story above includes a few quotes from a BOM weather forcaster, one of which:
"
"(Spouts) are like the willy-willy or dust devils you see in country areas but because they form over water, what you're seeing is actual sea water being drawn up within the very strong wind funnel."
However, in the photo, the spout clearly extends from a cloud to the sea, hard to see if the cloud is part of a storm cell but I'm guessing it is, therefore it's a tornado.
I have seen plenty of 'willy-willy's and dust devils (even had a large one pass over me on a school trip to the Pilbara), and there is often never a cloud in sight!
So to me, if there are no storms or no connection to a storm-cloud, it's a willy willy over land, a water spout over sea. If there is a connection to a cloud it's a tornado, no matter how slender.
Edit: added link.