Fair enough. Just tested it in Outlook '07 and you're right. I don't think it used to have that feature, though.
Of course, if you're using Exchange, there's no guarantees about the accuracy of the RFC2822 headers.
I was looking at Outlook 2003 actually. I'm pretty sure 2002 and 2000 also were OK. They had significant issues using Exchange remotely though. MS basically gives away Outlook 2003 licenses to Exchange users I think.
There are things I don't like for sure with Exchange/Outlook but I still find it does a lot. And in a >300k employee company, I don't have a lot of swing in the matter

As for the original issue, I can only suspect a backup restore.