How do I grant start/stop/restart permissions on a service to an arbitrary user or group on a non-domain-member server?

There doesn't appear to be a GUI-based way of doing this unless you're joined to a domain - at least not one I could find anywhere - so I did a bit more digging and I've found an answer that works for our situation.

I didn't understand what the string representation meant in the knowledge base article, but doing a bit of digging led me to discover that it's SDDL syntax. Further digging led me to this article by Alun Jones which explains how to get the security descriptor for a service and what each bit means. MS KB914392 has more details.

To append to the service's existing security descriptor, use sc sdshow "Service Name" to get the existing descriptor. If this is a plain old .NET Windows Service - as is the case with ours - the security descriptor should look something like this:

D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOC
RRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)S:(AU;FA
;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;WD)

We needed to grant permissions RP (to start the service), WP (to stop the service), DT (to pause/continue the service) and LO (to query the service's current status). This could be done by adding our service account to the Power Users group, but I only want to grant individual access to the account under which the maintenance service runs.

Using runas to open a command prompt under the service account, I ran whoami /all which gave me the SID of the service account, and then constructed the additional SDDL below:

(A;;RPWPDTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)

This then gets added to the D: section of the SDDL string above:

D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOC
RRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)(A;;RPWP
DTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)S:(AU;FA;CCDCLCSWRPWPDTLOC
RSDRCWDWO;;;WD)

This is then applied to the service using the sc sdset command (before the S: text):

sc sdset "Service Name" D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;
CCLCSWLOCRRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU
)(A;;RPWPDTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)S:(AU;FA;CCDCLCSW
RPWPDTLOCRSDRCWDWO;;;WD)

If all goes according to plan, the service can then be started, stopped, paused and have it's status queried by the user defined by the SID above.

I just had the same problem.
You could use SubInACL.exe from the Resource Kit. Download the standalone utility here: http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=23510

Use msiexec /a PathToMSIFile /qb TARGETDIR=DirectoryToExtractTo to extract the files if you don't want to install the .msi

1. Open a command prompt as Administrator
2. Go to the directory where you placed the .exe
3. Run subinacl /service SERVICE_NAME /grant=COMPUTER_NAME\USERNAME=TOP

T = Start service
O = Stop service
P = Pause/continue service

Full reference: How to grant users rights to manage services in Windows 2000
or type subinacl /help

Note: don't try subinacl /service SERVICE_NAME /perm as it could get you into trouble (lesson learned :P). The name could be misleading (perm != permission), as it deletes all permissions to all users (even Admin!).