in the article you list it states:
Originally Posted by http://support.microsoft.com/kb/912918
Special rules for adminSDHolder Protected Accounts
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.
does this happen to the account you are trying to send from ? if so then it probably is still being treated like a domain administrator. if not then you probably just need to make sure the correct send-as permissions apply to those mailboxes.