I've been facing this problem for days now, tried almost everything and still no luck, so I'm sorry if it's been asked before, but I'm truly hopeless.
Right now, my SGS3 works only on stock ROMs. Every time I try to install a custom ROM (JB or KK) I have a problem with the signal - either baseband, IMEI and everything is "unknown", or everything is good (IMEI not "0049...", there are full correct APNs) but it still displays the "error while searching for networks" message.
Fortunately (as I realized on other threads),I can always go back to square one, flash a stock 4.3, with no problems with IMEI or anything, but, you know, stock sucks.
I tried installing every modem I ran into, but nothing helped. Is there a secret step from stock to custom on samsung devices I'm skipping (I'm an ex-nexus user...)?