I have Windows XP and now when I try the Search option (whether that'd be right-clicking on start and then "Search..." or the "Search" icon in the Start menu or right clicking on a drive letter and clicking on "Search...", explorer hangs for a few seconds but no search box pops up!!! Where'd my Search go?
Well, I just tried a search and everything worked fine.
Well, have you had any viruses lately that could have corrupted your OS? Have you been deleting files that you should not have. What about a registry cleaner program? Been one of them. If all else fails then wipe everything clean and reinstall.