Server 2012 misreports failure mode on role installs sometimes

So, a fresh Server 2012 R2 install, attempt to install WSUS on it.

I get back the error that the installation failed because the server needed to be restarted. Restart it, try again, same error.

Look in the logs, I find I have messages of the following form in Event Viewer:
Update IIS-ISAPIFilter of package IIS-WebServer-Core-Package failed to be turned on. Status: 0x80070bc9.

Oh good, time to look up error codes. Lots of searching seems to think that was a firewall/antivirus problem, but this is a lab machine without an antivirus and with the firewall disabled. There goes that theory.

Looking around, I find a nice logon failure in my Event Viewer logs that clues me into the underlying problem:
Logon Type: 5

Account For Which Logon Failed:
Security ID: NULL SID
Account Name: MSSQL$MICROSOFT##WID
Account Domain: NT SERVICE

Failure Information:
Failure Reason: The user has not been granted the requested logon type at this machine.
Status: 0xC000015B
Sub Status: 0x0

Hm, WID (Windows Internal Database)'s service account is failing to start because it doesn't have the correct permissions?

So, it turns out, we have a GPO in our domain which assigns Log on as a service rights to a specific set of accounts, none of which is NT SERVICE\[...]. As a result, Windows Server 2012 does the following:

• attempts to install WID
• attempts to grant WID user log on as a service right
• attempts to start WID service, fails because user lacks said right
• fails with "Server needs to restart." (!?)

I worked around this quickly and dirtily by adding the account to Administrators and granting Administrators that right on the relevant subset of the domain, but this is obviously not a remotely Good Idea as a long-term solution.

Just wanted to write this up so that people who run into this have an easier time than I did diagnosing it.