Both the customer and I had noticed that the search function in the Catalog section did not narrow down the selection.
The total amount of spaces on the tenant (Data + Shared + Managed) is by coincidence exactly 100.
Deleting or adding a space, making the total amount of spaces not equal to 100, makes the search functionality work again.
Looking at the requests sent when searching for Spaces in Catalog from the developer tools in Firefox (network tab with the XHR filter):
With exactly 100 spaces, we see that no 'name' parameter is shown
With 101 spaces, we can see that a 'name' parameter is shown ('admin' in this case)
Shoutout to Elias for looking into this with me.