I’ve either personally worked with these companies or have had them recommended by people I trust. As with anything of this nature, your mileage may vary.

MessageNet

messagenet.com.au – MessageNet is my preferred supplier and have used them on several medium sized projects. I’ve found their support excellent.

redcoal

redcoal.com – A reliable Australian SMS provider. They offer a free trial to get started.

Value SMS

valuesms.com – I haven’t used them, but heard that they are reliable.

Clickatell

clickatell.com – Clickatell is probably one of the better known providers. They provide a nice selection of API’s if you’re developing your own applications.

I’ll add more as I come across new services in my travels.