Update from me:
Microsoft has worked diligently on this issue and we've resolved some of the issues I was having. We're actually seeing three distinct issues.
1. mails that are large (resolved) were not making it through. Resolution was to update the machine.config with maxRequestLength set higher. Be careful though, lol, I apparently messed up big time doing this once before. Note I have not been able to make this work by altering web.config in the EWS directory...
2. mails that have undisclosed recipient lists are not making it through. I believe Microsoft is working on this issue.
3. mails that have alternate character sets, particularly in the subject line, are not making it through. I believe Microsoft is working on this issue too.