SFC is clear, and CheckSUR is clear - the only significant errors in the CBS logs are ones like these, just after a reboot....
Code:
2014-06-18 12:42:03, Info CBS Exec: Uninstalling Package: Microsoft-Windows-InternetExplorer-Package-TopLevel~31bf3856ad364e35~amd64~~9.4.8112.16421
2014-06-18 12:42:03, Info CBS Exec: Package: Microsoft-Windows-InternetExplorer-Package~31bf3856ad364e35~amd64~~8.0.7601.17514 is already in the correct state, current: Superseded, targeted: Superseded
2014-06-18 12:42:03, Info CBS Exec: Skipping Package: Microsoft-Windows-InternetExplorer-Package~31bf3856ad364e35~amd64~~8.0.7601.17514, Update: Internet-Explorer-amd64 because it is already in the correct state.
2014-06-18 12:42:03, Info CBS Exec: Uninstalling Package: Microsoft-Windows-InternetExplorer-Package~31bf3856ad364e35~amd64~~9.4.8112.16421
2014-06-18 12:42:03, Info CBS Exec: Uninstalling Package: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421
2014-06-18 12:42:03, Info CBS Exec: Uninstalling Package: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421, Update: Internet-Explorer-amd64
2014-06-18 12:42:03, Info CBS Exec: Unprojecting Package: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421, Update: Internet-Explorer-amd64, UninstallDeployment: amd64_microsoft-windows-i..explorer-deployment_31bf3856ad364e35_9.4.8112.16421_none_c2658da8ebaeca79
2014-06-18 12:42:05, Error CBS Failed. Attempted to uninstall a version of a non-driver component that is not installed, version: 0X900041fb04025, component: x86_microsoft-windows-ie-ieshims_31bf3856ad364e35_9.4.8112.16421_none_600cd2b3b47f5448, owner: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421.Internet-Explorer-amd64 [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS Failed to mergecomponent [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS ComponentAnalyzerUninstallDeployment: Failed on update: Internet-Explorer-amd64 [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS Failed to execute item[0] in Package: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421, Update: Internet-Explorer-amd64 [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS Failed to execute execution update. [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS Failed to execute execution package: Microsoft-Windows-InternetExplorer-VistaPlus-Update~31bf3856ad364e35~amd64~~9.4.8112.16421 [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CBS Failed to prepare execution [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Info CSI 0000000e@2014/6/18:16:42:05.366 CSI Transaction @0x1e4b740 destroyed
2014-06-18 12:42:05, Info CBS Perf: InstallUninstallChain complete.
2014-06-18 12:42:05, Info CBS Failed to execute execution chain. [HRESULT = 0x80004005 - E_FAIL]
2014-06-18 12:42:05, Error CBS Failed to process single phase execution. [HRESULT = 0x80004005 - E_FAIL]
Please post the C:\Windows\windowsupdate.log file - it may show us more of what's going on.