SPO Search Malfunctioning

I learned today that on one of our sites, when an editor (or myself as admin) do a search for a simple keyword or phrase, we get results we're searching for on that site. However, everyone else is not getting any results. I walked one user through it, changing her permissions all the way up to full control, but she was still not able to get search results.  I had several other users (varying levels of permissions) try to pull results, even using words that are visibly on the front page of this site, and magically the search does not yield results. What is going on? Any one else having this issue?