I just jailbreak my 3GS on 4.3.3 with sn0wbreeze. The phone was already officially unlocked, now I have no service and on baseband 05.15.04
What went wrong?
It is possible , it is locked to Optus. If you don't get a new carrier setting when you put in the other sim card, then you can only use Optus.
Usually an iphone bought under subsidized rate and you have a contract, it is locked.
One more way to test it out is to restore to stock firmware and use the other carrier sim to activate, if itunes says sim not supported, then it is carrier locked.