Samsung I9300 - Network unlock fails
I got the phone unlocked at a local mobile phone dealer for € 20. This worked.

Generally I'd say it is interesting how this network SIM lock comes from, because my phone never has been locked or branded by a provider. The stock firmware worked with different providers. The problem only appeared for the custom ROMs.

And be aware when changing your SIM card! I broke mine 2-times only by exchanging it (probably scratching the chip's surface) and had to buy a new one and get the old number transferred to the new.