Are you running BPS for Exchange?
It sounds like the user account is stuck in users pending delete at the moment, as the information from the database/mailbox has not been successfully cleared. I'd try re-creating the BlackBerryServer mapi profile, and then restart services. Also, when you restart services, check for errors from the BlackBerry Messaging Agent in the application log.
Also, run IEMSTEST.exe from the BES' utility directory. This utility will test to see if the BES has permissions to the user's mailbox if you are on exchange. Try to run the test against the user that is not deleting correctly, and ensure there were no errors. If there were, report back to us.
To re-create the mapi profile, reference the following:
BlackBerry Search Results
EDIT: I see your name is dominodongle, so I may have been jumping ahead of myself with my response