Have you flagged any custom roms already? I think I read somewhere that if you have a nand backup of your stock rom, you can reflash that and get your imei back, but I can't remember where I saw that. If you haven't flashed ant custom roms, but have a rooted stock rom, and custom bootloader you can run nvbackup from a terminal emulator to back it up, and nvrestore to restore the imei. As for efs, I don't know if that's included in the backup, nor do I know what it is...
Sorry if this isn't the answer you were looking for, I'm not quite sure how everything works on the s3 as I have yet to root and read all about it