Microsoft has redesigned its autoupdate pages into one central portal: http://update.microsoft.com/. You no longer need to go to Office Update separately, for example.

On that central page you also find help links. Use these and read them thoroughly if you have a problem. They list the most important problems and their solutions.

Please see also:

Updates are not installed successfully from Windows Update, from Microsoft Update, or by using Automatic Updates after you repair a Windows XP installation
http://support.microsoft.com/kb/943144/

If the Automatic Updates don't work well, you can try to reset the updater. There are some utilities around, like:

• Windows Update Check Utility – Currently unavailable, please check here.
• How to obtain the latest version of the Windows Update Agent to help manage updates on a computer

And there are some relatively long manual procedures.

Older pages, that may still be relevant, are:

HOW TO: Troubleshoot Problems Connecting to Windows Update
http://support.microsoft.com/kb/818018/

Problems When Viewing or Downloading From Windows Update
http://support.microsoft.com/kb/193385/

Kelly's Korner
http://www.kellys-korner-xp.com/xp_w.htm
Scroll down to Windows Update.

Four hints on Marc Liron's Web site:

• Windows Update Fails—Error 0x800B004
  http://www.updatexp.com/0x800B0004.html
• Windows Update Fails—Error 0x800A138F
  http://www.updatexp.com/0x800A138F.html
• Cryptographic Service Error
  http://www.updatexp.com/cryptographic-service.html
• Windows Update Keeps Prompting Me To Install A Patch
  http://www.updatexp.com/windows-update-keeps-prompting.html

If all these don't solve your problem, describe your problem in the Windows Update newsgroup news:microsoft.public.windowsupdate, where you will get good answers.