[Verizon Samsung Galaxy S III] net-cat:
After more hours than I'd like to admit playing around with this, I finally got it working. Here's what I did.

Requirements:

A rooted stock ROM of the VRALF2/4.0.4 vintage. I used stock.vzw_root66.tar. (MD5: f0772544da403dfe15b163eed53b6dba) (SlimSnoopOS linked a similar ROM above, and I've quoted them at the bottom. I'm not sure if it's the same ROM.)

VRALEC.bootchain.tar.md5 (MD5: 8c45b7fbacefb65b173e2b4679bcf8e4)

CWM6012TouchVZW.tar.md5 (MD5: b9fa5adc0f76006794338affba30ffb1) If you know of a later version that can be used with ODIN, you can skip a few steps.

VRLE6.bootloader.zip (MD5: 959cf38b9c6dda345529664283f3a4ce)

Latest CWM or TWRP. (I used CWM Touch 6.0.45)

The Terminal Emulator APK file. (http://jackpal.github.com/Android-Terminal-Emulator/downloads/Term.apk) You can get it from Play Store after you've flashed back to stock, but I find this to be much less of a hassle.

I'm going to assume you know how to boot into and use recovery.

NOTE: I don't know where to get VRALEC.bootchain.tar.md5, CWM6012TouchVZW.tar.md5 and VRLE6.bootloader.zip. They were on my hard drive from when I first rooted my phone.

NOTE: Do NOT let the stock ROM install any updates.

Starting with my CM11 M3 install, I did a nandroid backup. (Recovery is CWM Touch 6.0.4.5, but I doubt that matters.)

Used ODIN to flash to your rooted/stock ROM. (Section 5 of this tutorial is what you want, if you don't know how to do it.)

Once the rooted stock is flashed, you'll need to do a data/cache wipe from the stock recovery to get it to boot.

Boot into the ROM and enter *2767*3855# into the dialer. This will do a factory reset. (This probably isn't necessary, but it's a step I did.)

Send a few text messages to test. (I sent them to Twitter.)

Unlock your bootloader and install a your recovery again. (Instructions provided in case you need them.)

Flash VRALEC.bootchain.tar.md5 using ODIN. (Same way as did the rooted stock ROM.)

When it reboots, immediately go back into ODIN mode.

Flash CWM6012TouchVZW.tar.md5

When it reboots, immediately boot into Recovery mode. (Vol+Up)

Use your recovery to flash VRLE6.bootloader.zip.

Reboot back into the stock rooted ROM.

Install Terminal Emulator from your SD Card. (The stock ROM has a rudimentary file browser called "My Files.")

If your ODIN recovery is not the one you'd like to use, install the correct one at this point. (Instructions for installing a CWM img file in case you need it. This is the risky way of doing it, though.)

Launch Terminal Emulator and enter su and press enter. Choose "Allow" when it comes up.

Enter dd if=/mnt/extSdCard/<your recovery file name> of=/dev/block/mmcblk0p18 substituting your recovery filename without angle brackets. DO NOT press enter yet.

Double check this command! You can brick your phone if you get this wrong!

Then press enter.

This would be a good time to back up your IMEI if you haven't already done so.

Launch the Maps application, turn on your GPS and let it get a lock. If you don't, when you boot back into CM11, you probably won't have working GPS.

Reboot into your recovery, wipe data/cache and restore your nandroid backup.

At this point, you'll be running your preferred ROM with an archaic radio.

DO NOT UPGRADE YOUR RADIO. The moment I upgraded my radio, the problem came back!

CM11 M3 will work just fine with the old radio, even if it's little slow to send. I've rebooted several times over the last few hours and it still works fine. (Time will tell if it's a long term fix or not.)

If someone who has the problem and has access to the VRALF2 radio, please try it and let me know if it solved the problem without having to do the above procedure.