Read the Start Menu Search Guide for a detailed explanation:
viewtopic.php?f=7&t=1588In summary, Classic Shell uses its own fast search for finding app/program shortcuts and Control Panel settings. The advantage of this is that this search continues to work even if the Windows Search service is disabled.
But Classic Start Menu relies on Windows 7/Vista Search index for finding files (documents, pictures, music, videos and other files). This index is a database so only the files included in this database by Windows will be returned in the search. The indexing is done in the background by a system service. As far as the Start Menu's Windows Search integration is concerned, this means that only indexed files will be returned in the search results (exactly like the Windows 7 Start Menu). For non-indexed searches of files in other folders, you must use Explorer, or add the folder to the index.
So Classic Shell itself has no file/folder search functionality of its own, it relies entirely on Windows Search indexer for that.
You can expand the scope of what is searched (indexed) by adding folders to a Library or to Indexing Options in Control Panel.
Also, shell extensions (think of them like plugins/addons for Explorer) called IFilters and Property handlers extend the ability of Windows (and thus the Classic Start Menu) to index the contents and metadata of many more file types.