Are you sure you're not still slithered or whatever it was?
I've no idea what you are talking about! Let's try and work it out
1) You lost your phone
2) The phone was rooted and ROM'd (whatever that means)
3) You contacted your network provider to bar your phone/sim
4) Having barred your phone with them, you wonder if they can actually bar your phone.
What is rooting and ROMing? Does that affect the built in safety measures all phones have?
Any network provider should be able to bar your phone on the hardware level - that's the built in safety measure. If you haven't done something odd to change this, then it should be barred fine. No doubt if it's picked up by a less-than-scrupulous person there are ways around it, enabling them to sell your phone.