Look in their File > Options > Search

There's a choice there "Improve search speed by limiting the number of results shown" which might be the cause.

The Troubleshooter when you click the 'Indexing Options…' button might help.