Not sure whom you spoke with, but this is the order we used to archive by, I am checking to see if that is still the case.
LAST MODIFICATION TIME (only if the item has been archived or restored previously otherwise the next 3 attributes in order)
MESSAGE DELIVERY TIME
CLIENT SUBMIT TIME
CREATION TIME
If the first doesn't exist it moves onto the next etc, if none of them exist then it will fail.
Documents/attachments:
LAST MODIFICATION TIME
CREATION TIME
Normally the Last Modification will be blank, but in your case you have restored the messages so I think that quailifies as a modification.
regards,