Resolved Windows search isn't running

After reinstalling XP SP3 this is what happens:
When I want to do a windows search a 'helpful' window opens telling me: "Windows search isn't running. To start it click the Start Menu, point to All Programs and then click Windows Search. "
And when I follow instructions I am told: "Windows Search isn't running etc. etc. ........" Despite the fact that in "processes" it shows up as using 50% cpu.
Now the really infuriating part is: when I want to shut down my computer a little window opens telling me that WindowsSearch.exe is running and should be allowed to close down first. I have to tell it to forget about saving and stop it in spite of dire warnings of "losing data ".
And the indexing service insists it is enabled but seems stuck on "snooze 15 minutes ", even though "snooze" is not enabled.
I've tried reinstalling, with the same result. Could my CD have become corrupted? It installed without that pesky problem before!

It is not a malware/virus... problem because it's a clean, new replacement HD, on a clean computer.

 

Hi Evan,
Sorry for not replying immediately, I didn't get near my puter till now, so couldn't experiment.
Anyway, I've now followed your advice, installed Windows Search 4.0 and all seems to be working perfectly. No idea why search wasn't working before. Doesn't matter now, main thing is: problem solved.
Thank you!