All users will need “send as” permissions on the mailbox. How are permissions being set up now? Are they using delegates (not a good idea)? Are they assigning permissions to the mailbox? Please provide those details. Also, are they Exchange accounts? If so, what version of Exchange? Thanks.