DISM /StartComponentCleanup fails, but /ScanHealth reports healthy

My WinSxS cleanup task was giving the "Last Run Result" of The component store has been corrupted. (0x80073712). No problem, to elevated command prompt and DISM.

>DISM /Online /Cleanup-Image /ScanHealth

Deployment Image Servicing and Management tool
Version: 6.3.9600.17031

Image Version: 6.3.9600.17031

[==========================100.0%==========================]
No component store corruption detected.
The operation completed successfully.

OK Great, should be ready to clean.

>DISM /Online /Cleanup-Image /StartComponentCleanup

Deployment Image Servicing and Management tool
Version: 6.3.9600.17031

Image Version: 6.3.9600.17031

[==========================100.0%==========================]

Error: 14098

The component store has been corrupted.

The DISM log file can be found at C:\WINDOWS\Logs\DISM\dism.log

Odd, let's fix that up.

>DISM /Online /Cleanup-Image /RestoreHealth

Deployment Image Servicing and Management tool
Version: 6.3.9600.17031

Image Version: 6.3.9600.17031

[==========================100.0%==========================]
The restore operation completed successfully. The component store corruption was repaired.
The operation completed successfully.

Let's be safe and re-scan.

>DISM /Online /Cleanup-Image /ScanHealth

Deployment Image Servicing and Management tool
Version: 6.3.9600.17031

Image Version: 6.3.9600.17031

[==========================100.0%==========================]
No component store corruption detected.
The operation completed successfully.

And on to cleanup

>DISM /Online /Cleanup-Image /StartComponentCleanup

Deployment Image Servicing and Management tool
Version: 6.3.9600.17031

Image Version: 6.3.9600.17031

[==========================100.0%==========================]

Error: 14098

The component store has been corrupted.

The DISM log file can be found at C:\WINDOWS\Logs\DISM\dism.log

I'm totally at a loss. How can it report as non-corrupted, repaired and corrupted all in quick succession?

Anyone considering relation of this question, sfc is of no use either.

>sfc /scannow

Beginning system scan.  This process will take some time.

Beginning verification phase of system scan.
Verification 100% complete.

Windows Resource Protection did not find any integrity violations.

TL;DR: My SxS store is non-corrupt, repaired and corrupted. At the same time. Unsure how to fix.

The original poster fixed the problem by rebooting - dism /Online /Cleanup-Image /RestoreHealth is indeed the command that needs to be run for Windows 8 and newer.

There is another tool that can be helpful in this kind of situation: CheckSUR, also known as the System Update Readiness Tool. You can download it for Windows 7 and before from KB947821.

According to this Microsoft blog post, CheckSUR can usually fix corruption in the component store, but when it can't, it's still possible to use it to identify the affected components. Near the end of the CheckSUR log is a list of packages; these entries correspond to Windows updates and KB articles. Get the MSU from https://support.microsoft.com/kb/NUMBER-HERE and place it in the \Windows\CheckSur\packages folder, which you may have to create. Re-run CheckSUR after you've done that for each package.

Note that CheckSUR may take a while to do its thing.