I am a Mail plug-in developer and several users have already reported this problem to me. It does not seem to depend on account settings and happens with some incoming messages as well. It is a specific message structure that triggers the problem, and the same messages are handled OK on Mac OS X Snow Leopard. Moving to another folder helps because Mail changes the internal structure of the message (structuring of the mime parts, header order, etc.), but it may not help always.
The problem can be replicated reliably by saving a message as raw source, converting it to the mbox format (by prefixing it with a From line) and then importing it on a different computer.
I have reported the problem to Apple (it is also present in the current developer preview of 10.7.2):
http://openradar.appspot.com/radar?id=1313404
The more reports Apple gets the more likely they are to fix it. So please report the problem too if you have experienced it. You can do so even without a developer account:
http://developer.apple.com/bugreporter/bugrptform.html
(In that case, I recommend saving a message from which attachments cannot be removed as raw source, uploading it to a web server and including a link in the bug report. Feel free to reuse the text fo my bug report.)