did you by any chance change your XP Start Button to say something else using an exe editor such as ResHack? I did that once, and had the same problem with the search feature. When I changed it back to the original explorer.exe with "start", it worked perfectly.
Comments
Must be something simple - a windows resotre is Out OF The Question.