Well, while I don't live in Australia and I don't know their laws and such, I can offer this advice:

I've changed my password but what else should I do? Can they still get online when we're online? Do they get cut-off when we disconnect?
If my ISP is wrong and they really should be doing something what should I say to put the fear of God in them?
Changing your password on a dialup account is definitely the first step in securing it. Make sure it's a GOOD password (6-8 chars both upper and lowercase with special characters and at least one number), something like gR8eSt1& . Keep in mind, most ISPs probably don't allow more than 8 chars so making something 10 chars in length won't help because it'll authenticate against the first 8 (like passwd will let you change your pw in unix/linux to any length, yet login doesn't give a shite after 8 chars?! what's up with that? Time to abuse the open source movement and go fix that! hehe...)

They can't get online with your account if you've changed the password (they'll constantly fail). As for the bill, you might get shafted on it, but I'd tell your ISP that you didn't authorize anyone else to use that account and that you can prove you were away on vacation and that if you DO have to pay for it, it'll be something like 10 bucks a month for 20 months, hehe...if they get pissy, cancel your account and go somewhere else because if you're forced to pay for someone else's abuse and blatant breaking of the rules, then your business is deserved elsewhere.

If they still give you grief on it, tell them that from this point on, nobody from any other phone number should be allowed to use your account, period and go so far as to verify on the phone that you will not be responsible for anyone else's charges on your account if they choose to bill you for their wrongdoing. They probably won't agree to that but you've stated it and if something else happens, you have written documentation for all of this.

As for their "It's against privacy laws.", tell them that your privacy was violated when they broke into your account and now, it's up to the ISP to handle charges and any police action against them. I would think they'd try to help you out but it seems they don't care. I'd start looking at other ISPs, my friend....

Hope this helps. Oh, this is also my opinion...