Well Ricebus,
I would tell you to do a clean install to fix the problem, but you said you already did that. Since it is happening when you do a Windows Update, I would uninstall that update that you suspect is causing the problem. Once you have it narrowed down to the one(s) that is causing this, I would hide the update so it will not show up in Windows Update anymore. These tutorials will show you how.
How to Uninstall a Windows Update in Vista How to Hide or Unhide a Windows Update in Vista
Hope this helps,
Shawn