Just a thought: would it help to have different messages.like "this message was deleted by author" and "message deleted by moderator"?
Are messages numbered? I mean, if there clearly are no messages between 80762 and 80765 in the archive, that would indicate that the messages in between were deleted.
btw I support the year-mm-dd format over the USA custom
