[nole172]

I had this problem this past week when our Exchange Server box crashed and we rebuilt it. Everthing was OK until we rebooted our BES server and then nothing worked. Had the "unable to open mailbox, may have been deleted" message when trying to do anything with the user in the console. From researching the problem, I guessed the hidden Blackberry folders for each BES user in the exchange mail store had gotten corrupted. I used a utility from MS called mdbvu32 to access each users' profile and delete the hidden Blackberry folders in the message store within Exchange. It would be very tedious for a large number of users, but is a lot easier than exporting their emails, deleting and recreating their accounts and importing.

The mdbvu32 tool is a little tricky to use. Be careful!
Backup the mail store and also the BESMGMT database on the SQL Server.
Delete the user using the BES console.
Run the mdbvu32 tool on the BES server while logged in with the besadmin account. When you open the tool, you can select a profile, but click new and create a profile for the first user.
Open a new session, open the mailbox store, go to the Root folder. Double-click the Blackberry folder to see the subfolders.
Choose empty folders from the list of functions and click call function.
Close that window to go back to the root.
Select the Blackberry folder and call the delete folder function. Close the mailbox store, close the session and exit.
Use the BES console to add the user again.
Repeat for the next user.

This worked for me - I had the exact same symptoms as the first poster, but please use cautiously. These are rough directions because I am writing this from memory.

Update: I just noticed that post immediately above this appears to offer a similar solution with a different tool. That tool might be easier to use...