I'm gonna chime in.
From what I've found, modifying the APN settings is always a temporary fix or, if anything, a "placebo effect" of sorts. I'd like to consider myself a bit of a power user when it comes to my phone, so I tend to document and take notice of every bug that comes up, and I've found that the MMS issue is prevalent across every ROM for the Droid 4 - and it only ever happens with the AOSP Messaging app. MMS messaging, at least for the AOSP Messaging app, is always a hit-or-miss; when you reboot the phone, try to send an MMS message on the AOSP Messaging app. If it goes through, great! It works. If it doesn't go through, you'll need to reboot the phone until it works. The methods that I've found to "work" for others - erasing database files in the phone's filesystem, changing APN settings, et cetera - are always a hit-or-miss solution; correlation does not equal causation, and I've found that, regardless of the steps taken to fix the problem, it always comes down to the luck of the reboot. It's a snake oil fix, basically, and has nothing to do with fixing the problem, save for the fact that rebooting the phone has a chance to temporarily fix it, regardless of whether or not you changed APN settings or deleted a file or did whatever. In other words, rebooting the phone can either disable MMS for the remainder of its uptime, or enable it for the remainder of its uptime; it's always random.
I don't know why the AOSP Messenger app is the only SMS/MMS app that has this happen to it. I've heard that GoSMS, Handcent, and Verizon Messenger always work, but I'd rather not use a third-party texting app.
Tl;dr Until the bug is officially fixed in a future ROM build, the only way to temporarily "fix" the problem is to reboot the phone until MMS works. A good way to test if MMS Send/Receive works is to try to send an MMS message to somebody.