This issue is one of two things:
1. CDO.dll mismatch between BES and Exchange
CDO.dll must be the same version or higher on your BES. IF it's lower you will get this issue.
The BESAdmin account CANNOT be a domain admin or any admin. The only time the BESAdmin is in an amdmin group is when the BES is on a domain controller, the account should then be in the built-in admin group only. Also Send As must be set in Exchange System Manager at the Server level and should inherit down to the mailbox store and public folder store level.
Review this article from RIM, BlackBerry Search Results
Let us know how it goes.