Windows Update KB3023266 is installed on every shutdown of the computer. On next start, the update log shows an additional entry like this:
Name: Vulnerability in Windows Application Compatibility cache could allow elevation of privilege: January 13, 2015 (KB3023266)
Date: 27.01.2015 13:45
But it is still possible to install it manually and the same update will install automatically again and again and again on every shutdown, restart.
I tried WindowsUpdateDiagnostic and MicrosoftFixit with no success.
How should I fix it. Manually resetting the whole windows update is a long and tedious thing to do(http://support.microsoft.com/kb/971058). Would it even fix this problem?
I tried to install it manually (http://www.microsoft.com/en-us/download/details.aspx?id=45454). It completed with success but the problem persists, see my comment to Overminds answer.