Lmao every phone in China that you haven't heard of the brand has Dual-Sim or the manafacturer has a Dual-Sim phone aswell.
There are two allright ones in the Australian market.
The DUALSIM Phone Company NSW Australia | Dual Sim Mobile Phones & PDA | Dual Sim Card Cell - some random new brand in Aus which makes only dual sim phones. They look nice and stats aren't bad.
Id also have a look below at this website, if you see anything interesting try to find it on Dealextreme (read at bottom) first as its likely to be half the price.
Dual Sim Mobile Phones - Australia's LEADER in Dual Sim Phones - seem to be importing a lot of the obscure chinese phones.
Philips 699, Samsung D880/D980 and a few other Samsungs seem to be for sale on the internet.
If you don't really mind having amazing quality, stylish looks or known brand or care about 3G features and stuff. I would suggest you go on Dealextreme (look it up) and buy some dodgy dual sim iphone rip off for like $100. They have a lot of dual sim phones and are all cheap just have a good look around at whats available and read reviews/check its compatible with the networks over here before you buy.
EDIT: Hmm yes deffinetely read the disscusions before you buy, one of the cheaper phones came with a mosque as the background (changable) but when you turn it off it quotes a verse from the Qur'an loudly through the speaker xD. but for $60 AUS including shipping this phone which has a touch screen and seems to support real video among other video formats seems to be a good deal, especially considering some guy said you can change the sound played when you turn it off.