That behavior sounds like a consequence of our having archived some categorically older threads. Can you provide a sample search string you're using? And are you using "Advanced Search" with any search parameters? Or are you using the simple search bar toward the top of every page? Ultimately, it sounds like the missing posts are archived ones that still exist in the database but are viewable only to admins; that's something we've documented and will continue to see about possible fixes.