Problem: Spotlight will only find some files, and fails to re-index. I had a stubborn Spotlight that wouldn't find files; I searched high and low for solutions. I found some help in this post, but it never permanently fixed the problem. While trying to reindex using Apple's instructions, I noticed that if files are corrupt, Spotlight fails.
Solution: Boot into single user mode (Command-S at startup) and run the file system check by typing /sbin/fsck -fy (this command will be shown on screen in single user mode). Virus scanners are another way to find corrupt files. I found the corrupt files with the files system check and fixed them, and now Spotlight is reindexing correctly. This fix should work for any similar Spotlight issues in 10.5, too.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20080122085658347