Have you tried deselecting all the updates in the list and just running them one at a time to see if its one particular pending update that is causing the failure?
I had a 2008 Server box once that had a similar problem, simply wouldn't update no matter what I tried. Luckily it had a 'check online for updates' option that did run ok. Never solved the original problem, had several identical boxes that worked fine.
If you've reinstalled multiple times and problem persists, I'd try the installing one at a time option then, if no joy, contact Microsoft as they will give you support.