I am working in SP online. I just realized that for some lists/libraries the search box is not working at all.
Try redindexing the list: List Settings -> Advanced settings -> Reindex List
If there are multiple lists on same site affected you might want to index whole site: Site Settings -> Search -> Search and Offline Availability
Do note that in SPO it takes some time before reindexing kicks in so it might take some hours or a day until reindexing has full effect.
The problem got solved by itself after 1 day. It seems MS takes some time to re-index lists. So next time I'll be waiting before alarming!