You mean they can't go into Messages on the device and delete them or they don't reconcile when deleted from Outlook?
If they don't reconcile then check the settings on the device to see if it's enabled. Go to Messages>Click trackwheel/trackball>OPtions>Email Reconciliation. Ensure that Wireless Reconcile is on. If that option is missing then the Desktop[CMIME] service is corrupt. Delete it from the device and resend the service books from the BES.
If they can't delete them from the BB then the Messages DB is probably corrupt and might need to be deleted but I don't see that happening for all users. I think it may be the service book is corrupt.
Reconciliation is always a device issue, never the BES.