I've noticed that the search indexes only those files which have previously been opened with some application.
For example, searching for a presentation returns 0 results initially, but once I navigate to the file in Nautilus, and open it with LO - it becomes, along with the folder hierarchy it is in.
I've tested this primarily with files on another partition (where my home folder is) and on another disk (where most of my documents are).
Why is this so? Is it a bug or an intentionally missing feature? (Windows 7 finds all files whether they've been opened or not.)