Sometimes Spotlight does not find a file or a file's contents when searching and re-indexing does not help with it.
The culprit was a wrong permission on the file, which was generated when saving it from one Mac to another via Go » Connect to Server. When trying to move such a file from one folder to another on the destination Mac, it always asked for the Administrator password.
It turned out that such file had permissions as 'Nobody Read and Write.' Adding the Administrator as Read and Write did not help to find it with Spotlight.
The workaround is to create a new folder, drag and drop the files or folders containing files that are not found by Spotlight, select this new folder, do File » Get Info and check Apply to enclosing items to change the permissions.
Like magic, a second later Spotlight finds such files and their contents.
What I do not know is if there is a way to automatically find and repair the permissions of such files, other than doing it manually on a one-by-one basis, or for the whole user account home folder.
[crarko adds: I can't say I've seen this particular one before, but it does seems logical that Spotlight wouldn't index a file that has no read permissions. The other question to ask is how the permissions got whacked in the first place.]
Mac OS X Hints