Does archiving already archived messages means deleting them?
I just tried this in a non-Gmail account and the message has vanished! It is in none of my folders, including the trash. You can use Time Machine on Mail to get your messages back. Also, I suggest reporting this bug to Apple http://apple.com/feedback/mail.html

(In Gmail accounts, the message goes away for a few minutes until the next time Mail synchronizes with the server.)