It is possible to rescue Date for most messages, and it may be possible to do something about Message-Id. I don't have the details to hand tonight.
Sorry to hear about this. What was bad about the backups? Anything there ought to be an aox command to help check?
