Recently wrestled a major problem with six Blackberry in a BES/Exchange environment.  Here is a checklist which emerged.

1. Email has to go from ..blackberry.net and *.blackberry.com to the BES admin’s email box, and quickly.  Make sure Internet email will go to the BES admin email box. If it doesn’t go quickly, solve that problem first.
2. The BB tech said that a recreation of encryption password, is a good thing to try.  It’s the least invasive, and least destructive.
3. Another good thing to try is a removal and reactivation.  This is not a wipe!  Just remove the entry in the Blackberry server and say yes to the second removal step also, add it again, set the activation password to something simple (one letter is good), and then go through activation on the handheld itself.
4. Regardless as to whether it is an encryption re-creation or a reactivation you are trying, the user’s mailbox will receive an email from something.something.blackberry.net, which the Blackberry server has to pull automatically out of the user’s mailbox.  This is done by MAPI.  So MAPI has to be working well in server mode on both the Blackberry server and the Exchange server…which means you had better not have ever installed Outlook on either one, this can be a cause of difficulty.  If for any cause MAPI is failing, the re-creation or activation email will stay in the user’s mailbox.