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
As MichelZ, says, your manager is correct if you're on a 2003 domain. Though, regardless of that, I ideally wouldn't want to alter my policy for one single account, either. The real issue is that the service is attempting to log on with an incorrect password.
I'm posting this as an answer because the solution is to stop the issue altogether and figure out why a service is attempting to log in with the wrong password. If it's due to the password expiring then this can be sorted in AD Users and Computers rather than by reconfiguring the password policy:
This is standard practice for service accounts