Please review this article: BlackBerry Search Results
This will show what errors in the logs to look for and how to set the permissions, there's even flash video.
Also, there are relevant Microsoft KB article numbers there as well for reference.
If any of the affected users are part of any "protected" groups then they lose the permission needed to send email.
Please read the article thuroughly.