Have you re-indexed your database? I'll bet this is probably it. This has been an on-going problem when I scan new files in (it's definitely a bug in SMHD/SMHD+ sill present since the beta test period when I reported it - might be a limitation of the database back end being used on this SM product, and thus, not "correctable"). You always need to re-index the database (only takes a few minutes - quick bathroom break or coffee break). Failing to do this it will kick back partial (or no) results where you should be expecting results, even though in the "View All" it shows all records accounted for after the scan. This goes not only for initially scanning but every time you scan additional material.
Basically the index terms/records aren't getting updating during scanning, so the boolean search still refers to the 'old' indexing, thus the new data is invisible to search.
The additional thing to check, depending upon which SM product you have, that you've upped the limit on search results from the default limit or disabled it. I'm pretty sure its an indexing problem, but this could just be something to check just in case.