Spotlight's great power stems from its use of the Index to search file content and metadata. This is, however, also the program's Achilles' heel. When the index is incomplete or becomes corrupt (neither an especially uncommon occurrence) then Spotlight doesn't work. It won't tell you of course and the only way you find out is when, for example, you fail to find a file that you know is there.
There are lots of fixes for a bum index, most of which will work to get the program up and running again -- but one round of that may (sensibly) cause you not ever quite to trust that Spotlight is actually doing what it is supposed to be doing, namely, searching your hard drive, or at least all of the nominally indexed parts of it, for files. The solution, at least until Apple develops a fallback utility that can search in the absence of an index (Panther's cmd-F, anyone?), is Easyfind, which can be found at
http://www.versiontracker.com/dyn/moreinfo/macosx/11706 . Easyfind performs filename searches without an index. It's not as fast or as elegant as the pre-Tiger OS X utility, but it's comprehensive, and more reliable than Spotlight. Spotlight can do some pretty neat tricks but when I really and truly need to find a file, I use Easyfind.