Domain admins are not the only groups affected by the Send As issue. Search
BlackBerry Technical Solution Center for "send as" or "revoked". You will find RIM's Kb for it which also links to some useful Microsoft kb's as well.
Because your "ordinary" users lost the permission it means that they are linked to another group that is considered protected.
Also, after apply said permissions, restarting the BES does not fix it. It's the permissions cache on Exchange that must clear. You do one of the following:
1. Stop the BlackBerry Router service for 20 minutes, or 2 hours, depending on what is set on your Exchange server
2. Restart the Information store on Exchange
The whole point is to prevent the BEs from accessing the users mailbox which uses the permissions cache. The cache will not clear unless you prevent access to it so it can clear or restart the info store which flushes it immediately.
Read the RIM Kb, all the info is there.