I forgot to mention one - very important - step that needs to be done. If your users were Domain Admins, even if you strip the Domain Admin rights from them, they will still be considered a protected account. Therefore it is necessary to follow a few additional steps to do that. Here is the informaiton you will need for that:
(UPDATE ON THIS: I am sort of inserting this paragraph after the post was published. I am still debating whether this is really necessary, especially if you strip Domain Admin rights. On one hand research suggests that it is... but then I was able to get around this for some users).
Special rules for adminSDHolder Protected Accounts
If you use the script to grant the Send As permission for a mailbox owner that is also a domain administrator, the Send As permission will not be effective. We strongly recommend that you do not mailbox-enable user accounts that have domain administrator rights or that are adminSDHolder protected.
The adminSDHolder object is a template for accounts that have broad Active Directory administrative rights. To prevent unintended elevation of privilege, any account that is protected by the adminSDHolder object must have access rights that match those that are listed on the adminSDHolder object itself.
If you change the rights or the permissions on the adminSDHolder object for a protected account, a background task will undo the change within several minutes. For example, if you grant the Send As permission on a domain administrator object for an application service account, the background task will automatically revoke the permission.
Therefore, you cannot grant the Send As permission to an application service account for an account that is protected by the adminSDHolder object unless you change the adminSDHolder object itself. If you do change the adminSDHolder object, this will change the access permissions for all protected accounts. You should only change the adminSDHolder object after a complete review of the security implications that may occur with the change.
To associate a mailbox with an account that is protected by the adminSDHolder object, follow these steps:
1. Start the Active Directory Users and Computers management console.
2. On the View menu, make sure that the Advanced Features option is selected. If this option is not selected, the Security page will not be visible for User account objects.
3. Create an ordinary user account to act as the mailbox owner.
4. Assign the ordinary user account a mailbox on an Exchange server.
5. Open the properties of the new mailbox owner account.
6. In the Exchange Advanced box, grant the Full Mailbox Access permission to the protected administrator account.
7. In the Security page, grant the Send As permission to the protected administrator account.
8. Click OK to exit the properties of the mailbox owner object.
9. Right-click the mailbox owner account object, and then click Disable Account to disable the account for all logons.
