I have been dealing with little things since upgrading. Overview: I went from 14 to 16.
I have noticed and maybe this is coincidence. If I impersonate the account and the account admin is email@example.com and send a message as firstname.lastname@example.org it seems to fail with a similar message. Another couple things I noticed is the host name was not associated with the IP anymore and the domain needs a host name.
I added the DNS host name to each spot:
Under the domain, there is a spot below enable/disable the domain a host name is required.
Settings->Bindings (each IP)
A tech replied to my ticket and suggested going back to 15. So over a weekend I would go from 14 to 16 and back to 15. Not the greatest solution, but I may have to take it.
Before I do this I am hoping someone else has a solution.
For those having issues are the people with the issues a domain administrator?