I ran into a very strange situation on an old Windows Server 2003 server at work today. The Windows Search service could not be started, stopped, or have its permissions modified by anybody -- not even an administrator!
I first noticed there was something wrong when I tried to apply a Security Configuration Wizard template. Among other things, the template disabled Windows Search, which wasn't being used. It kept failing with an "Access Denied" message. It was very misleading, because it kept pointing to access being denied to a configuration file. In hindsight, this must have been a bug in the way it reported errors, because access was actually being denied via the Security Configuration Manager (SCM), the "service" that runs all other services on Windows.
Before I got a chance to break out with all the fun diagnostic tools (such as SysInternals' ProcMon), I realized that the Windows Search service (WSearch) was still started in the Service.msc MMC. I tried to stop it and got "access denied" which I found to be quite odd.
I then opened up another MMC and added the Security Configuration and Anlaysis snap-in and also the Security Template snap-in. I quickly ran a quick audit and looked at the permissions on the Windows Search service. "Everyone" had "read" access, but only SYSTEM had "Full Control" access. Bummer.
At this point, applying a custom template would do nothing (I didn't have access), but I tried anyway. No luck. So what does one do in this case?
You need to log on as the SYSTEM account. This is actually pretty easy to do if you are an administrator. First, make sure you are either logged on at the console or using the console session in remote desktop. Now, open a command prompt and type "at 10:53 cmd /interactive" minus the quotes. Also, replace "10:53" with the time that is exactly one minute from now. What this does is it tells the old legacy "at" process scheduler to open an interactive command prompt one minute from now. Since there is no direct way to log on as SYSTEM, this is second best. Since everything run via "at" uses the SYSTEM account and since it's told to interact with the desktop (but only the console session), you get a command prompt running as SYSTEM. Fun!
Now, use the "SC" command to apply new permissions. This can be most easily done using the "sdshow" and "sdset" flags. Look up help on SC at Microsoft's website for more information. All permissions for "sdshow" and "sdset" use the SDDL formatted descriptor. If you don't like SDDL, the easiest way to fix this is to boot-strap permissions for your locked up service. Use "sdshow" on a service you know you can manipulate. I used w3svc. Then take the exact string shown and apply it to the locked service using "sdset." Now your regular admin account can use the afforementioned friendlier "Security Configuration and Analysis" and "Security Templates" MMC approach which has the nice GUI. Of course, if you are well-versed with SDDL, you can just modify the permissions directly from the command line.
I can't say why this happened, but it's an old server and has had a lot of roles, so I speculate that some third party application must have screwed up service permissions at some point.
Either way, mystery solved!