VirtualBox 4.3.20 stops working after Windows Update [duplicate]

You have to remove the Windows Update KB3004394 (or install this update, which apparently just removes the old one). The whole procedure is explained here.

After uninstalling that update, also uninstall VirtualBox, restart, then install VirtualBox, restart again.

Apparently others have had this issue too. The update seems non-critical and should cause no security issues when removed:

The Windows Root Certificate Program enables trusted root certificates to be distributed automatically in Windows. Usually, a client computer polls root certificate updates once a week. After you apply this update, the client computer can receive urgent root certificate updates within 24 hours.

For others, the problem may be caused by using custom themes (i.e. with a patched theme DLL). This could be fixed by running sfc /scannow, but it did not apply in my case.