[T-Mobile, Samsung Galaxy SIII] RevMike:
I figured this out after a struggle, so I figured I would pass along the info in case it helps anyone else.

I'm running CyanogenMod 11 (Android 4.4.4 Kit Kat AOSP based) on my T-Mobile Galaxy S III. I'm on vacation in Mexico, and I had planned to use my Verizon HTC Rezound (aka HTC Vigor) as a phone with a local Mexican SIM card from Telcel. Once I was in Mexico I discovered that the Rezound does not support the GSM/HSPA bands commonly used in North America. It should work fine in Europe, but I could only get Edge service. I decided to try to unlock my T-Mobile Galaxy S III to see if it worked any better.

The free unlock methods I found seemed to require the stock Service Mode applications - so I needed to install a stock rom. I tried to flash a rooted stock 4.3 ROM but the instructions didn't seem to work. The baseband I was running seemed to be too new for the unlock method, which was noted as working with 4.1.1. I tried to downgrade the baseband. It still did not work. I tried flashing a stock rooted 4.1.1 image, and it still did not work. At some point while trying things I realized that no baseband was getting reported in the about screen and no IMEI number was being reported. The phone wasn't even trying to connect to the network. Googling around made me think I hosed my EFS partition. I didn't have a backup.

I hoped that if the EFS partition was corrupted, it might get rebuilt. I used 'dd if=/dev/block/platform/msm_sdcc.1/by-name/efs of=/storage/extSdCard/efs.img' to make a copy of the current state of the efs, then I deleted all the files. I restarted the phone. So data got written to efs, but still I couldn't connect to the network. I didn't have a windows computer with Odin on my trip, by I tried used heimdall with my Mac to write a stock 4.1.1 rom. Still no luck. Not only was the network not working, but the touch screen and buttons were erratic and it would spontaneously reboot. Also, it would generate no sound at all. I figured I practically had a brick. I tossed it in my suitcase and left it until I got home.

When I got home I used ODIN to write the most recent (Android 4.3) root66 stock rooted image. On reboot I got sound back. That was promising. I used dd again to restore the contents of my EFS partition. I was able to connect to the network again. I installed the latest snapshot build of CyanogenMod 11 and everything seems to be working.

I finally put the pieces together. The EFS partition in older roms is formatted with a FAT filesystem, and in new roms it is formatted with an ext4 filesystem. At some point as the phone is upgraded, the EFS partition gets updated to the newer filesystem. Older basebands can not read the data from the ext4 filesystem. If you do not have a backup of the FAT version of your EFS partition, you can't downgrade to the older baseband.

I don't know the precise transition point, but the baseband that comes with 4.3 can read the ext4 partition fine, but the basebands with 4.1 need the FAT partition.

If you open a terminal shell on your phone or with adb shell, then type 'mount', you'll see a list of mounted volumes. The entry for the EFS partition will look like this...

/dev/block/platform/msm_sdcc.1/by-name/efs /efs ext4 rw,seclabel,nosuid,nodev,noatime,user_xattr,barrier=1,journal_async_commit,data=ordered,noauto_da_alloc,discard 0 0

The first field is the location of the partition. The second field - in this case '/efs' is the mount point. The third field is the filesystem type. Here you see 'ext4'. On your phone, look for the line where the second entry is '/efs'. If the third entry is 'vfat' you can downgrade to older basebands. If it is 'ext4' you can't go to very old basebands unless you have a backup of the old version of your EFS partition and you know how change the filesystem format. Anyone with decent Unix/Linux experience should be able to do that - it isn't hard - but I don't have the old EFS backup to try it out, so I won't try to give any instructions here.

I hope this saves you some trouble.