Based on what you've described and my limited knowledge, that could happen when you're downloading the "header" of the message instead of downloading the "entire" message from your mail server.
You could click "Send and Receive" again, after you marked the message to be deleted, or you could go to Tools/Options/Email Setup and then select Send/Receive to configure download option for each of your e-mail accounts.
