Redlabour: Does this happen to you if you move one of your own threads? If so, then it's likely a problem with the phrases - check to make sure that the move phrase doesn't have "delete" text in it.
If the phrases are fine, then I suspect the users may be mistaken, or mixing up their PMs as it would happen for everyone on your forum rather than just a few users.
Let me know how you get on
Thanks,
Alan.