Oh my God, this was hard to find!
Ok, so I started this new job as an Exchange 2003 admin at a new company. The previous admin had done all sorts of tweaking to the permissions in the Org (manually editing registry keys, dis-allowing permissions inheritance in ESM, etc). Of course, he left no documentation.
So I'm looking at the properties of the server in my office and notice that in the field for where the Message Tracking Log File directory is located I see:
Access is denied Facility: Win32 ID no: c0070005 Microsoft Exchange Management
I looked all over the net before I finally found the answer: LOCAL SERVICE must have Read permissions on the following registry key:
HKLM\SYSTEM\CurrentControlSet\Control\SecurePipeServers\WinReg
I even tested removing this permission on a lab server and sure enough it's easily replicated. I present this information so that perhaps you won't get as frustrated as I did.