I am not seeing this problem on 3.4d. I created 200 test documents in a single category and then used Alfresco Explorer advanced search to search for them and all are returned.
One difference is that my repository is virtually empty. Yours probably isn't. I wonder if you are running into the large Lucene result set limitation problem discussed in this thread (and many others).
If you are running against a production repository, can you try on a local, empty repository and see if you get the same results?