Do the affected users have any deny Send As, as of course this will overwrite any allow permission?
Can you log on to a desktop workstation as the BESAdmin, fire up Outlook and send an email on behalf of another user successfully?
Have you checked things like the AdminSD holder permissions? This KB may help with that:
Link