Being from OZ myself I can tell you I got my STS shipped to me with all the parts (except the wheels) for $165 via USPS. It arrived in perfect condition and I bought the wheels separately. I did get the guy to dismantle the suspension part though. I also had an LTS frame sent the same way for $130 - not dismantled from The Sellution.
How small a frame was it? There is a 79" combined length and girth limit to Austrailia for Priority and Express International services. How can you get a frame in a box under 79" (12" frame) or did they send it First Class International Mail? Dismantling got it small enough?
The STS was a 16" and the LTS 18" and I'm pretty sure they were both were sent Priority, Although the LTS could have been sent 1st class. The top mount on the STS suspension was undone and the rear triangle was pulled forward over the top tube. The dude dismantled a few bits and got the forks and everything else in there bar the wheels. Lots of bubblewrap to finish it off.
Just depends on how much work you want to put into it to dismantle it...