As an example over here in NZ, Air NZ are actively recruiting pilots for their Regional operations (ATR, Q300, B1900).
Minimums have reduced significantly for all fleets over the last couple of years and it would be worth having a look on the careers link supplied on the Air NZ website. Being an Australian I'm assuming you'll have the right to work in NZ if that is something that rocked your boat. Good luck.