Yep. Sometimes flashing stock roms restores the IMEI where it's a case of it disappearing temporarily. But you've already tried that, and if this was the case with your situation, you would have fixed it already. I mean, you can flash a bunch of stock roms & maybe you'll get lucky, but it almost always returns with the first stock rom you flash in these cases.
If you have an EFS backup that you know is 'good' (I.E you verified its integrity with something like kTool when you made the backup), then you should be able to restore it with kTool/similar. If you've tried that & it doesn't work for whatever reason, the backup is obviously bad.
I would be very surprised if a Samsung service centre didn't fix it if you paid them. However, you will possibly find that a local mobile repair shop who isn't an authorised Samsung repairer will fix it more cheaply (that's certainly the case where I live).
I noticed you tried to restore the backup with EFS Pro (don't know why people insist on using this app, maybe it's the 'Pro' in the name ? I don't think I've seen anyone on here successfully restore with it), try with kTool (search here/Google Play).
What you do from here is up to you, but if it were me (having tried the things you've already tried), I'd be biting the bullet & getting it fixed tomorrow, because you can try a bunch of things that won't work & you'll still have to get it fixed in a week/whenever.
If it's important enough to cause you grief if it's lost, back it up. No excuses
Trolling for thanks is lame
Does Samsung's auto-brightness implementation crap drive you to self-harm ? A solution !
Most retarded thread on XDA in 2013