File names can have "funny" characters in them.
List the disk with a utility that provides a listing of the entire
disk, then use a hex editor to look at the names. That's in case
Notepad or Wordpad just ignored the funny characters.
Other issues would be, whether you have got "indexing" turned on or not.
Or, whether you are using WinXP standard search, or you have installed
about how your search is set up. If the search comes back pretty
fast, then it is probably using an index. Sometimes a particular
file type, or even an area on the disk (like the contents of your
emails) are missing a handler, and so the search system will not
give you a result for it.
Those are a few ideas you can look at.
My WinXP does not have Search 4.0, is not indexed, and generally,
when I search for something, it is located (slowly).
As an example of a search that might not have good results, I
tried searching for ".svn", and as far as I know, Windows
does not like folders with a leading dot. And yet, the vanilla
unindexed search facility on WinXP, was able to find instances of
Also, do not forget to check your search boxes, and see
if you ticked "Case Sensitive" by accident... Some of the
search tools I use have options like "Whole Words", which
prevents a sub-string from being detected, but I do not
see that as an option in Windows search.