Not until I came back to this thread this morning did it ever occur to me that the trigger was turning an email account off and on. It totally makes sense now because I would turn off an email account only during the weekdays, and I didn't seem to have the issue on weekends. So I tested the theory, and at least for me, that seems to be the cause of problem.
Here's how I tested it:
1. I closed the mail app by double clicking the home button and swiping up on the mail app.
2. Opened the mail app. Sent test email. It sent and was received.
3. I turned off a mail account.
4. Sent another test email from one of the remaining accounts. It did not show up in the sent folder, nor was received.
5. I turned the mail account back on.
6. Sent another test email from one of the remaining accounts. It did not show up in the sent folder, nor was received.
7. I closed the mail app again.
8. Reopened the mail app. Sent another test email. It sent and was received.
It may be just a just a manual fix for now, but I will be sure to either reboot my phone or close the mail app every time i turn an email account off or on. I have an appointment with the Genius Bar tomorrow (my second trip in). I will tell them what we've discovered (and what I've confirmed is the trigger to my email issues) and see if they know of any fix or can send this issue to the higher-ups for a permanent fix. I will come back and post an update after my visit. Or maybe an apple person will follow-up on this thread and chime in?
I would be interested to know... is anyone that has this problem not turning an email account on and off?