You can exmerge the mailbox to pst file, then blow it away, recreate mailbox and activate it by sending an email to it first. Then activate device. Then import mail back to a mailbox. I still beleive it has something to do with permissions. Are these user's account in any kind of domain admin groups?
I could resolve this by doing this 1) do an exmerge running exmerge as BESAdmin 2) Do a backup of the BB Handheld 3) Wiped the Handheld 4) Delete the user mailbox, Run the Clean-up Agent of MS Exchange and purged it 5) delete the user in the Blackberry Manager. purged it and restarted the services. 6) Add a mailbox to the user, reset the BESAdmin permissions, deleted the Outlook profile, create a new one. 7) Add the user in the BlackBerry Manager, configure a password for activation and activate it on the BB Device (Worked) 8) Resend back the pst that I exmerged before 9) done several tests (Send&Receive) on BB device and email client => problem done