Did a bit of research (sponsored by Windows 7:Inside Out).
Windows search uses the index from:
Start menu, Search Home folder, libraries and homegroup locations.
So, from these locations, if it's not in the index, it won't show up.
If you search from the Computer window, local drive root or local file folder, it will search for your term even if it's not in the index.
To check what's being indexed, search

for index and select Indexing Options (in the control panel).
You can also modify your folder's search options by:
Folder Options>Search:
When searching non-indexed locations>include system directories, and
How to search>Don't use the index when searching in file folders...
You can also specifically look for extensions by typing: ext:*.ost
It'll search subfolders when you add the wildcard.
Finally, to quickly add a location to the index, add the folder to a library. It'll then be indexed... apparently.
Finally, finally... if you want to obsess over your indexing status, look out for the Indexer Status gadget by Brandon Paddock.