The additional information is that it is the entire filter bar that is blocked, not just the search. A quick way for me to test is to select Audio for the All Media Items drop down.
If I go through the unchecked items in Block menu items: Not Selected and toggle them one by one, I never reach a point where the Media Library can be filtered.
If I check all, it is the same result.
If I select Block menu items: Selected and deselect all checkboxes, I can filter the Media Library.
If I check the items that were not checked under Block menu items: Not Selected, the filtering works as desired.
Could you explain, or point to documentation that does, what the difference is between these two modes in Admin Menu panel?