- The search service wasn't returning any results.
- They couldn't access the SSP administration page from the server.
This turned out to be the loopback checking feature in IIS. This feature prevents you from accessing a Web site with a host header from the same machine - for example, you can access http://machinename/default.aspx, but not http://hostheader/default.aspx. When you attempt to access a site under these conditions, you'll be prompted for credentials three times and then have access denied with a 401.1 Unauthorized: Logon Failed error. The giveaway was that the Central Administration site was set up to use the machine name, whereas the SSP site was set up to use a host header.
Because this is a single server environment, the search service is attempting to crawl sites, by host header, that are hosted on the local machine. In each case, access is denied with a 401.1 error and you end up with a very empty search index.
This issue became a fairly well known problem for SharePoint administrators on Windows Server 2003 environments, and usually arose when the server was upgraded to SP1. I've never come across the issue in a Windows Server 2008 environment before - I guess an update must have triggered the loopback checking feature in IIS7, but I'm surprised it wasn't enabled already.
Anyway, I followed the workaround here (Method 1), restarted the IIS Admin service, started a full search crawl and we're up and running again.