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.
Best Answer
You have to manually do this generating .resources from LocBaml and then merging the Resx and BAML resources using the Assembly linker.
The process looks something like this:
(everything on one line in a batch file).
You can put the above in a batch file customized for your project. Remember LocBaml has to in the same folder as your output files. You can add this as a post build task.