After working with MS Partner suppoprt newsgroups, I got the following answer on how to easily modify the adminsdholder object permissions to grant send as permission to the BES service acct. Their disclaimer (obviously) is that MS did not and does not endorse or recommend the following solution, although it works. Best practices aside, please do not hold me responsible (another disclaimer).
Remember to replace domainname with your own, as well as domainnameBlackberrySA (the name of your service account). Hope this allows some fellow CTOs to keep their jobs... And their temporarily useless Blackberries!
dsacls "cn=adminsdholder,cn=system,dc=domainname,dc=com" /G "domainnameBlackberrySA:CA;Send As"