I’ve filter the list by the few restaurant related categories you have, none of the entries seem to have “restaurants” in their name/address/nio/notes. So, the search is correct. If you want to search by the restaurant category(ies) using the searchable category drop down. That’s what it’s for. Then, if you need you could further refine the search by adding a keyword. Or you could search just by name with filtering by category.
Typing “restaurants” into the keyword search field is not going to filter the list by entries in the restaurant categories. use the drop down.
Or, use the Enhance Categories extension and disable the categories drop down, that way you can list an index of categories above the directory and even make the categories section in the entry card clickable to allow the user to filter by category.
Pick which you like best.
re: category count
That is odd. Can you try adding a dummy entry and then deleting it? Perhaps the counts, which are cached, were not cleared and you are seeing old counts.
Are the counts accurating on the Connections : Categories admin page?