I happened to stumble upon this one by chance-and I do admit I am really happy since
I am very familiar with the situation. It seems that a patch intended for the information store
changes the behavior of permissions thus causing lose of functionality of the aforementioned services.
For additional information on this topic please visit:
http://support.microsoft.com/kb/912918/en-us
http://support.microsoft.com/kb/895949/
And the post on the Exchange team blog:
http://blogs.technet.com/exchange/archive/2006/01/13/417440.aspx