Excellent and thorough article! Interestingly, I had a problem just last Friday where one of our Exchange 2003 servers was not delivering messages and the 'Messages awaiting directory lookup' queue was climbing.
I performed many of the troubleshooting steps above, suspecting a GC or networking problem. Eventually, I discovered that many of the folders under %SystemDrive%Program FilesExchsrvr were missing(!) I scheduled a CHKDSK on %SystemDrive% and restarted. I fully expected to have to run an Exchange setup/reinstall, but to my surprise all the folders were there after the CHKDSK and restart, and the mail delivery resumed as normal. BTW, there was no FOUND.000 folder on the server to indicate that truncated files were found.
Strangest thing I've ever seen, so I thought I'd share it with you.