Yes. There is no access rights listed that explicitly hide an object from search results. View > Browse hides an entry from both search results AND folder views.

How did they find a way to hide these files explicitly from search results, even they don't know how they did it.

Manage Entry Access bypasses Browse on folders. That's why you can see it in the folder. The search shows the documents the user is allowed to see directly.

I used the effective rights on the account to verify that Bypass Browse is not checked on the account we were using. Also the browse checkbox is checked on the document when using effective rights under access rights of an example document.

Is something set for the Everyone group?

No bypass browse on the everyone group, I used effective rights to see if it is applied by any groups at all. We always turn off bypass browse because we have enough horsepower to do it and it's a much cleaner view.

Manage Entry Access will implicitly grants Browse. Have you looked in the effective rights dialog to see where the user is getting View and Browse?