I’ve experienced what I believe is the same issue.
I set up the Admin Menu access for a couple of custom roles using the “Block menu items Not Selected” and when one of those user roles tried to search the Users list in the admin, they didn’t get search results and instead were directed to the WP admin dashboard.
I found this forum topic and went back to switch the Admin Menu access to be “Block menu items Selected” and swapped around my checked items. After saving and testing, the user role could then perform a search of the Users list.
So the admin search functionality doesn’t seem to play well with the “Block menu items Not Selected” option.