EDIT: With thanks to David Arno, a better option - download the uninstall folder from David's site, and run the following from the command line:
%systemroot%\$NtUninstallKB940157$\spuninst\spuninst.exe
Have come across a few Windows XP machines with incomplete uninstalls of Windows Search. Although the toolbar is removed and the entry is removed from 'add/remove programs', high CPU and disk IO is evident from processes such as 'searchindexer.exe' and/or 'SearchProtocolHost.exe'. The following will remove it altogether:
A. Try running the uninstall located in the 'c:\Windows\$NtUninstallKB940157$\spuninst\' directory
B. If that folder is missing, do the following:
- Delete the following reg keys, to make the installer believe Windows Search 4 is not on the system: "HKLM\SOFTWARE\Microsoft\Updates\Windows XP\SP3\KB940157" "HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\KB940157"
- Reinstall Windows Search 4. This will add the uninstall files back to C:\Windows\$NtUninstallKB940157$
- Now the uninstaller should be present in Add/Remove Programs again and can be uninstalled as normal.
With thanks to this thread.