Sometimes I search for a record that I know is present in a table, but see 0 results. If I wait a minute or two and search again, I find it as expected.
This is always in my largest table, roughly 5,000 records with about 75 different fields.
It seems obvious that the search feature takes time to index larger tables. If the search/indexing cannot be sped up, I would suggest putting in some kind of status bar or spinning wheel to indicate that the search has not fully loaded. It is troubling to search for a record, not find it, create a new one, then realize you have duplicates! (Yes, this happens…)