After removing that XP Antivirus 2011 malware, I had two XP machines that did not have the Automatic Updates service even installed, and therefore it would not run. After some googling I found the Microsoft KB883614 that addresses both this problem, and that of the BITS (Background Intelligent Transfer Service) missing. I’ve copy/pasted it for simplicity.

The Automatic Updates service is missing

To reinstall the Automatic Updates service, follow these steps:

1. Click Start, click Run, type the following command, and then click OK:
   %windir%\System32\rundll32.exe setupapi,InstallHinfSection DefaultInstall 132 %windir%\inf\au.inf
2. If you are prompted to insert your operating system CD, type the following path in the Copy files from box, and then click OK:
   %windir%\ServicePackFiles\i386

   Note This location contains the most recently updated service pack files. If you cannot use this path to copy the required files from, insert your operating system CD, and then click OK.

The Background Intelligent Transfer Service is missing

To reinstall the Background Intelligent Transfer Service, follow these steps:

1. Click Start, click Run, type the following command, and then click OK:
   %windir%\System32\rundll32.exe setupapi,InstallHinfSection DefaultInstall 132 %windir%\inf\qmgr.inf
2. If you are prompted to insert your operating system CD, type the following path in the Copy files from box, and then click OK:
   %windir%\ServicePackFiles\i386

   Note This location contains the most recently updated service pack files. If you cannot use this path to copy the required files from, insert your operating system CD, and then click OK.

Whether it be due to hard disk corruption, or more likely a boot kit or rootkit, you may need to rewrite the Master Boot Record.

Rewrite the MBR in XP:

Boot into XP Disk, repair mode, recovery console

Then type

fixmbr c:

and press enter

Vista and 7 (32 or 64 bit)

To run the Bootrec.exe tool, you must start Windows RE. To do this, follow these steps:

1. Put the Windows Vista or Windows 7 installation disc in the disc drive, and then start the computer.
2. Press a key when you are prompted.
3. Select a language, a time, a currency, a keyboard or an input method, and then clickNext.
4. Click Repair your computer.
5. Click the operating system that you want to repair, and then click Next.
6. In the System Recovery Options dialog box, click Command Prompt.
7. Type Bootrec.exe, and then press ENTER.