Default [Q] Changing ROM on a network barred phone

Hello. I had a quick search around but could not find a definitive answer to my question.
I have just purchased a Samsung I9305 that was imei locked through the Australian carrier Optus.
The phone had been lost so the owner rang and reported such.
When he found the phone in his wet weather gear a week later (It was for his business) He obviously could no longer use it
I purchased the phone from him after confirming the details. There is a company here that can unlock the imei and through talks with them I can unlock the imei for other carriers than Optus and other carriers on that network. I have no problem with this as Optus do not have the service and coverage I need So I am with Telstra.
I have upgraded roms and unlocked my S2 a few times

Now that the details are out of the way, my question is this:
I HATE phones that have all the carrier bloat on them. Can I change the ROM on this phone without problems (I have not looked yet but want an Australian Rom not associated with any carrier), or will the Imei lock come back if I do. I do not want to brick the phone or lock it from being used. I would go with a Telstra rom if I have to or at the very least root the phone and remove all traces of the Optus bloat

Thanks for any help in advance...and really hope that someone does not immediately link to another post I missed due to poor search technique