It sounds like the Messaging Agent is trying to retrieve a message for the handheld that doesn't exist in the account any more. -> "Document has been deleted".
The only reference I could find for it was:
"This warning message indicates that the original message could not be found in user's
mail file. This might be because the user deleted the message before it could be
forwarded to the handheld."
Are you running BES 2.1/2.2 for Domino?
No idea with the first one. It's not often that the Dispatcher will fail to Decrypt/Decompress.
Reboot?