How to search for Entries that have a particular Category set within a Matrix field in the Control Panel?
Very simple answer: you just type the category name (no matter whether it's being set within a Matrix field).
The reason this didn't work in the first place was that my search index hadn't been updated properly by the auto-running task that triggered after an XML import I did with the Feed Me plugin.
I simply had to rebuild the search indexes manually to fix the issue.