I'm having the above problem on Exchange 5.5 (SP4) (running on NT4 / SP6a).
(I am running Norton Antivirus for Exchange 2.0)
I've found KB-Q285021 which suggests using a different logon account to
start the service.
I've tried this and it still dosen't work.