Have you tried deleting the Desktop[CMIME] service book and resending it? Also, if you send them an email, read it on the BB then do a Reconcile Now, does the email reconcile?
What version of BES? Versions of MAPI32.dll on the BES and Exchange? How many users?
Have you toggled the Wireless Reconcile to OFF, saved it, then toggle it ON and saved it? Only new emails will reconcile after that.