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.

Thank you @Lugh but unfortunately this did not solve the issue. Good shout though I hadn't tried that.

To anyone who finds this post with the same issue - this was resolved by turning off Cached Exchange Mode