Windows desktop search has had alot of issues on Windows XP, therefore alot of people wish to uninstall it. Unfortunately, one of the many issues is the uninstallation of it.
First try uninstalling normally from add/remove programs.
Newer updates Edit
If you get this message, when trying to uninstall: "The update could not be removed because newer updates are installed. Please remove the newer updates first." Then you need to locate and uninstall the updates.
- Search for files that contain "windowssearch" in "c:\windows" and then run the spuninst.exe in the resulting folders until you find one that actually uninstalls.
- Try uninstalling them until you find one that actually uninstalls.
- Try uninstalling normally from add/remove programs again and if it still doesn't work, retry uninstalling from those folders.