Working for a major phone manufacturer, I had to clear a bit of this up, with a few links:
http://www.acma.gov.au/WEB/STANDARD/pc=PC_100581
and
http://www.acma.gov.au/WEB/STANDARD/pc=PC_100575
112 is GSM only, and will not work in the same way on 3G (or what Telstra chooses to call "NextG"). 000 is still your best bet, and as mentioned at the second link it maps internally to the same number as 112 in most newer GSM handsets anyway.
Long story short: learn and use 000. I wouldn't want to rely on an older GSM phone with no service contract in an emergency situation, would you?
