Just discovered the following blog post which explains how to fix it:
WSS Search: Your search cannot be completed because this site is not assigned to an indexer
Copied from there:
Go to Central Admin as login as the farm Administrator
Go to Application Management tab
Select SharePoint Web Application Management heading | Content databases
Ensure your web application is the one selected
Select your content database name
Under Search Server – select your server (if your search server drop down is disabled please follow the additional steps below)
Go to 12 hive folder and open stsadm.exe utility
Run the following command psconfig.exe -cmd services -install
Then run stsadm -o spsearch -action start (specify the farm account if required)
This process will register the search services within the SharePoint (WSS) farm and search service will now appear under central administration. Now you can click the service service and create a indexing schedule. After indexing job is completed for the given web application you will notice that search results appear as expected.
Step 7 means "Go to your SharePoint installation folder and open stsadm.exe".
Running these two commands and then running the indexer finally fixed this problem.