Yes, this is related to my other post. It's been a problem for quite awhile, and I figured I would post it as a succint question.
Definitely not related to certificate validity, since a restored message with an expired (or otherwise invalid) certificate is still a properly-formatted message as far as Exchange is concerned.
I opened cases with Symantec, but they were closed without resolution.
There have to be others who have run across this, so I'm going to keep throwing it out there every now and then in the hopes of encountering someone else who's seen it.
Regards,
Ethan