Unable to install updates in Server 2003 - all attempts fail

Scan the server thoroughly for malware. Also check the Link below:

http://support.microsoft.com/kb/890830

Automatic updates has an annoying bug - if the update fails once because the update file is corrupt, the web site doesn't download them again. It simply tries again. You need to reset the automatic updates system.

http://www.amset.info/windows/auto-updates.asp

Simon.

I have tried checking for malware and using the Malicious Software removal tool and I cannot update.
Also tried Mestha's alternative but that did not work. It would download updates again, and fail. Looks like it fails immediately as it starts instead of just trying to install it and then encountering problems and failing.

What tools did you use to scan the system for malware?

Symantec AntiVirus 10.1.5.5000

Use adaware and spybot S&D to scan for malware, and also use an online scanner to scan for further threats, like trendmicro's housecall:

http://lavasoft.com/
http://www.safer-networking.org/en/download/
http://housecall.trendmicro.com/

Ran S&D and Trendmicro's housecall as suggested, all found was cookies that where deleted. Attempted to install Ad-aware but received the following error:

"Microsoft Visual C++ Runtime 9.0 SP1 could not be installed. Please use Windows Update to manually install this update on your system.
Adaware setup cannot continue."

After cleaning my system, the updates still fail.

This is probably similar to what mestha has already posted:

Disable the Windows update service, then delete the contents of c:\windows\SoftwareDistribution\Datastore and c:\windows\SoftwareDistribution\Downloads. After that re-enable the windows update service and try getting updates again.

I had tried that before, but went ahead and tried it and still fails.
Here is the ReportingEvents.log, not sure if its of any help:
{EA3185DB-92CD-4D53-815D-E026C025C39E}      2009-04-02 09:02:05:790-0400      1      147      101      {00000000-0000-0000-0000-000000000000}      0      0      WindowsUpdate      Success      Software Synchronization      Windows Update Client successfully detected 5 updates.
{75033DB8-1EE3-4873-AECA-BF58971AD7CE}      2009-04-02 09:02:13:072-0400      1      162      101      {A955D161-692D-4635-B1CF-259A77942F00}      103      0      WindowsUpdate      Success      Content Download      Download succeeded.
{600E74CD-B574-4B9E-A03A-5A772F187F9F}      2009-04-02 09:02:23:963-0400      1      202      102      {00000000-0000-0000-0000-000000000000}      0      0      AutomaticUpdates      Success      Content Install      Reboot completed.
{D097D3F9-127D-4146-A6FB-2181A918634F}      2009-04-02 09:03:04:604-0400      1      162      101      {6C3D8170-F8A2-4C1A-9103-6946ED025B23}      100      0      WindowsUpdate      Success      Content Download      Download succeeded.
{A4A463F9-EAAB-4760-ACF1-71DDBA0F2DAA}      2009-04-02 09:03:06:776-0400      1      182      101      {A955D161-692D-4635-B1CF-259A77942F00}      103      80070643      WindowsUpdate      Failure      Content Install      Installation Failure: Windows failed to install the following update with error 0x80070643: Security Update for Microsoft XML Core Services 6.0 Service Pack 2 for x64-based Systems (KB954459).
{91E5204E-6582-4688-9A4D-A9797C4CAE67}      2009-04-02 09:03:46:667-0400      1      182      101      {6C3D8170-F8A2-4C1A-9103-6946ED025B23}      100      80070643      WindowsUpdate      Failure      Content Install      Installation Failure: Windows failed to install the following update with error 0x80070643: Microsoft .NET Framework 3.5 Service Pack 1 and .NET Framework 3.5 Family Update (KB951847) x64.