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.
Best Answer
There isn't functionality built-in to Windows to do what you're looking for.
The idea below is a cheap hack and could easily be subverted, but it might get you what you want w/o using third-party software.
If I were going to do what you're trying to do, I'd build a security template that adds "Users" to the "Deny logon locally" user right assignment, and a second one that removes it (i.e. sets it back to the stock "Guest" only). Once those are built and tested (be careful testing it-- it'll stop even "Administrator" from being able to logon locally) I'd write a script to apply the security templates using a scheduled task. At the appropriate time, apply the template to prevent interactive logons, and then apply the template to restore the ability to logon interactively.