Perth seems... Well, let me just say that I seem to have a lot less issues finding movies and books and so forth over here. That said, I still have some (it looks like I might be done with the Far East Bracket for the moment), and I have found a very good rental place, but still.
Also, have you checked kino.com.au
? I haven't looked at the pricing options, but it might be worth considering.