It's a sad situation we're faced with where it's easier to find something from amongst the billions of web pages on the internet using Google, than it is to find that damn Word document you created last week. Windows' Search function is a fickle beast, but there are a few things you can do to tame it, and make it work for you.
First off, you need to configure Search to be as efficient and effective as possible. The easiest way to activate Search is with the <Windows key> + <F> combination, or you can drag it from the Start menu onto the desktop, or into the Quick Launch bar.
When you first fire up Windows XP's Search, you'll be confronted by an animated character. To disable it, right click and choose Turn off the animated character or, if you really want to make sure it's gone (or you just draw some kind of sadistic satisfaction from surgically removing it yourself), you can enter the registry and change your search interface back to the Windows 2000 style. Go to HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Explorer/CabinetState. Create a new String called Use Search Asst and set the value to no. Lo and behold, Search is back to its old self.
If you do want to use the XP style, you can still have more control over your Searching options, and also suffer less redundant clicks, by setting it to Advanced mode. Open Search, go to Change Preferences | Change files and folders search behaviour and set to Advanced.
One way to improve search performance is by switching on the Indexing Service. This uses idle CPU time to make a database of all your files, which is then used to assist in searching. This can speed up a search, but it will mean your system will resort to crunching in its spare time. If you find this slows your system down, you can turn it off through the Change preferences button in Search, or by running services.msc from the Start | Run command (or <Windows key> + <R>). Locate the Indexing Service, Stop it, go to its Properties, and set it to Disabled.
Indexing is not perfect though, as it doesn't index all file types, which makes it hard to find obscure files, such as those installed with applications or games. To force the Indexing Service to index everything, Run compmgmt.msc, expand Services and Applications and right click on Indexing Service. From this window, tick 'Index files with unknown extensions'.
Search also has a small blockage when it comes to searching for text within certain files. Originally Microsoft set it so Windows would ignore all files that are not registered with a filter, although recent updates and Service Packs have added many more file types. If there's still a file type that Windows is not searching, you can manually add a text filter to the file by Running regedit, and browsing to HKEY_CLASSES_ROOT and the file extension you're interested in. Then create a new key called PersistentHandler, and in the key, set the Default string value to {5e941d80-bf96-11cd-b579-08002b30bfeb}. Restart, and you should be able to search for text within that file type.
If you have lots of compressed CAB or ZIP files as archives, and don't want Windows to search within them, then you can disable this feature by unregistering the relevant files. Open a command prompt and type regsvr32 /u zipfldr.dll, and then regsvr32 /u cabview.dll. If you want to re-enable the searching within archives, then you need to reregister the files by typing regsvr32 cabview.dll and regsvr32 zipfldr.dll.
If you find you use a lot of advanced search options such as searching for hidden files or within subfolders, you can set these as the default using the registry. Run regedit and go to HKEY_CURRENT_USER/Software/Microsoft/Windows/CurrentVersion/Explorer and you can enable the following settings by making their value '1'. CaseSensitive; SearchSubFolders; SearchHidden, which will search for files that Windows normally hides, like system files; SearchSlowFiles, which searches tape backups attached to the system; SearchSystemDirs, which will search within system folders, like C:/Windows.
Finally, once you've searched your system to within an inch of tolerance, you can clear your search history by once again delving into the registry. Go to HKEY_CURRENT_USER/Software/Microsoft/Search Assistant/ACMru. Here you'll find one or two folders. These contain file/folder searches and text string searches. Delete the content of these to wipe the slate clean. You can also disable the saving of search terms by turning off AutoComplete in Internet Explorer.