Are you using Search (in the sidebar) or Quick Switcher (the pop up that searches only filenames)? If Quick Switcher, perhaps you crossed the threshold where it searches differently?
Do the searches that fail have anything in common? Could you give some examples?