Why can a user grant themselves the Log On As A Service right?

It sounds like there is a group policy that defines the accounts that are granted Log on as a Service. Because you are an administrator you have permission to grant this privilege, but when the group policy re-applies the privilege will get removed. The next time the service stops it won't be able to start.

You should either change the scope / filtering of the policy so this machine is exempt from it or use the policy to grant the necessary privilege.

INFO FROM COMMENTS: To check if a group policy is applying the setting use the resultant set of policy wizard (rsop.msc)
If you want to apply this setting to many computers or can't remove an existing policy that defines this setting then use group policy to define it. There is a technet article that explains how to do this.
To check the current local security settings use secpol.msc - expand Local Policies then select User Rights Assignments. This will show the currently applied settings. If you have sufficient access and there is no group policy in effect then this will allow you to edit the current policy. If the add / remove buttons are diabled then a policy currently defines this setting.

If there is no policy in effect, then allowing windows to grant the user the right is perfectly fine and is just a convience feature provided by windows. As Jez discovered, if a policy IS in effect then it is pointless fighting it. Policy generally re-applies every few hours and will keep zapping any changes you have managed to make. (Although the service will carry on working until it stops for some other reason). Jez mentioned that he things a service is identified by a LUID generated at install time. I don't know if this is the case or not, but the Log On As A Service user right is not restricted to any particular service. So it won't make any difference WHAT service you want to log on as. One danger of letting windows assign the right for you is that you may forget to remove previous accounts and end up with a huge list of accounts that have the log on as a service privilege and no need for it.

So to answer Jez's comment a little more directly, if there is a policy in effect, there is no point finding ways round the disabled secpol.msc UI. The UI is disabled as a warning to you that any changes you manage to make will not be retained. In this case, editing the policy is the way forward, either to grant the privilege or to stop making that setting so that it can then be assigned locally.

EDIT: You seem to think that granting a domain user this priviege is somehow different to granting it to a local user. It isn't. If the PC/Server in question doesn't have any group policy applied then you open secpol.msc, go the privilege in question, double click, click add and then select the account you want. I've just tried this on a domain joined laptop and the add user dialog actually defaulted to the domain. If I wanted to pick a local group then I'd have to change the location.

If you double click the privilege then I assume you see the list and the add / remove buttons but the buttons are diasabled so you can't edit the list. This can't be becuase you are adding a domain account becuase you haven't yet selected whether to add a local or domain account.

I've run into exactly this problem at work, the service I was installing was only going on one PC so changing policy was not an option. We moved the PC in question to an OU where no policy applied, then I could grant the privilege without issue.

The reason you can grant the privilege the round-about way is that policy just disables the UI, it doesn't actually change the permissions you have. It does however re-apply itself periodically, which is why the setting gets overwritten.

That article is describing ADAM (Active Directory Application Mode), which is quite different than your stock-standard Active Directory installation... Just worth considering.

Opinion time - I also believe that when you install (or reinstall) a service, it generates a UID for it in the registry. Some of it's settings are probably tied to that, including authentication.

Lets get this straight -

1. You have a service running under your user account (in services.msc it displays your user account next to this service)
2. To get this working in the first place you gave your account Log On As A Service rights
3. Following a reboot or reinstall of the service, the service fails to start with a login failure error
4. To fix this, you simply re-enter your credentials in the service configuration and start it

This implies that there is a problem with your saved credentials, NOT with you periodically losing the login as a service right.

First off, I would recommend creating a new user account to run this service under rather than using your credentials, set the password on the account to never expire and grant the account logon as a service rights. Best practice is to always use a dedicated account for software running as a service rather than re-purposing user accounts

Then see if you get the problem again, and if you do, try to work out exactly what was done to cause this to fail, i.e. Do you need to re-enter the credentials every time the server is restarted ?

Also, why are you reinstalling the service periodically ? Is there some other problem with this software ?