This could be because of Conversations. If you delete the message in the message list, you are actually deleting the conversation. Try turning conversations off (Menu > View > Conversations > Disable Conversations) and see if the problem persists.
This would not have been the problem in Andy’s post above, because conversations were not implemented before last year.