Thanks hugely for your help. I've already read through those threads, but I assumed firewalling wasn't an issue as Phex doesn't show the flame icon. Could it still be an issue that's preventing search results, and could there be any other reasons?
Thanks for the info about Library.MaxResultsPerQuery.
I'll start implementing a few of those points and see how we go.