@Miles Holt, RE: Granting Send As to domain admins.
KB 9121918 discusses this. In fact there's a new revision just published this morning that has some more specifics and references around the adminSDHolder issue. Explicit instructions for editing the adminSDHolder object were omitted from the article, to avoid giving the impression that we recommend editing it for mail purposes. However, if you just follow the links.... :)
I'm sorry about the hassle caused by this change. We know it's not easy. There was a lot of discussion about whether or not to do the change, because we knew it would be a pain for many administrators. In the end, we decided that the security improvement was valuable enough that we should make the change, including backporting it to Exchange 2000.