[Galaxy S 4 Q&A, Help & Troubleshooting] gadhafy:
I think i solved this!!!

You were ABSOLUTELY right. I had done NOTHING wrong, my IMEI had been blacklisted by a weird mistake of a mobile company.

I'll explain my jourey, in the hopes that it can help somebody, since, I HAVE A SOLUTION for every single case of this issue.

1) When I got my gt-i9500, of course I rooted it, then i proceeed to flash PAC-ROM on it, but I had to go back to Stock (Arrow Modified Version) since PAC-ROM is FULL of glitches ans bugs.

2) After a week of being using ARROW, i got the "NOT REGISTERED ON NETWORK" problem. Not instantly, no, AFTER A WEEK OF USING AS MY DEFAULT ROM. I got really scared, since I DIDN'T MAKE A BACKUP OF MY EFS FOLDER, and when I review my IMEI, it wasn't even the 00049... generic one, it was null/null. So i shat my pants, thinking I had ruined my S4 for good. But I started reading. First i had to get my IMEI back to its original form, and then work around the network issue (THAT'S THE ORDER, ACTUALLY)

3) So I downloaded a whole bunch of modems and tried one after one, with no success, some of them put the generic IMEI on my phone, some of them got my IMEI back to null/null. I was worried and drinking industrial quantities of wine at this point. So i went for the obvious but way more boring solution. I TRIED FLASHING STOCK ROMS on my S4. I live in Perú, so I only have 2 choices to do this, and actually my carrier stock rom is not even listed on SamMobile.com (I'm on Nextel Peruvian 3G network). The 2 choices i tried, neither got my signal or my IMEI BACK. I started going desperate, but keept on reading.

4) Tried the MTK Droid Tools to recover my IMEI. I had never even used The ADB android interface before, but learned rather quickly. Got my S4 connected, shell rooted, and still couldn't change my IMEI; since MTK Droid Tools (and please trust me on this one) ONLY WORKS FOR THE CHINESSE/KOREAN VERSIONS OF THE S4. So don't even bother, you might learn ALOT about the android ADB interface, but won't fix your IMEI.

5) Finally I started downloading a bunch of Stock roms in order to get my IMEI fixed automaticaly by flashing them through ODIN. And the I stumble upon THIS ROM: http://www.sammobile.com/firmwares/3/?download=17396 WHICH SEEMED like a divine answer from heaven since, just by flashing it, got me back my ORIGINAL IMEI.

6) At this point i had discovered that INDEED the MODEM: I9500UBUBMG9 does get your IMEI back to its original state. (That's your answer). SO, I was in a Stock rom, with my original IMEI, bu had NO FREAKING SIGNAL WHAT SO EVER. STILL HAD THE "Not registered on network" FREAKING problem. So I, finally, gave up, came here, and got the answer that It might had to do with my IMEI being blacklisted. I refused to believe so, since there are this stories on the internet, that you can actually screw your EFS folder by installing a custom AOKP rom without backing it up, and that there's this "RF CAL" file that only samsung knows how to fix and once it's corrupted, you won't be able to connect to any network, ever. BUT HERE'S THE THING, THAT story IS A LIE.

7) I went to NEXTEL (My carrrier) support (They sold me the phone) today, and YES, OMG YES, my IMEI had been blacklisted, AND HERE'S THE CATCH: ANYONE (At least that can happen in my country) ANYONE, can call your mobile operator, reporting your phone has been stolen, and the op will block NOT ONLY YOUR NUMBER, but your freakining IMEI, blacklisting it, and making it IMPOSIBLE for you to get connected on ANY network.

SO Here is my conclussion to this WEIRD case:

1) If you have the NOT REGISTERED ON NETWORK and you have the WRONG IMEI issue (Meaning, your IMEI is the generic: 00049... or Null/Null) , flash via ODIN, THIS STOCK ROM: http://www.sammobile.com/firmwares/3/?download=17396, just... flash it, I DON'T CARE IF YOU'VE READ THAT YOU JUST NEED THE MODEM, I garantee that if you flash this stock rom, your IMEI will go back to its original state.

2) If your S4 is on an Stock Rom, and you have your original IMEI; and you still can't connect to your network, It means your original imei has been blacklisted, and you NEED to talk to sammy or your carrier to fix this, or contact someone who can undo this situation.

That's it. I hope that my journey helps someone that is trying to get this "NOT REGISTERED ON NETWORK" issue solved, as I've been trying to for the entire weekend. Just... don't give up. http://xdaforums.com/images/smilies/good.gif