Hi Gibson, It looks like you were right on. Select users lost their Send As rights. I manually added the BesAdmin account to the broken users, checked the options to Send As and Receive As, and all was well.....for an hour (until AD ran). After AD ran, some users lost the Send As option, while others retained the Send As option. I'm digging more into the problem now, but thanks for pointing me in the right direction.
Scorpius, No changes have been made to this server at all for a couple of weeks. No changes in AD, Restores, Deletes, Firewalls, proxies, etc. It simply stopped working out of nowhere yesterday after two weeks of running perfectly.