Ok, this was a timely lesson learned.
If you are getting the following error trying to search a Windows Sharepoint Services 3.0 (WSS), you might be experiencing the same problem we did…
No results matching your search were found. Check your spelling. Are the words in your query spelled correctly? Try using synonyms. Maybe what you’re looking for uses slightly different words. Make your search more general. Try more general terms in place of specific ones. Try your search in a different scope. Different scopes can have different results.
The gist – if you want to crawl/search WSS content, you will need an NTLM authenticated website (ie. not basic). But you can have both – NTLM for search, basic for UPN (protected by SSL of course)…
To ensure that the index component can crawl content within the Web application:
• Configure at least one zone to use NTLM authentication. Ensure that the search content access account has the Read permission level to content accessed through this zone. You can do so by creating a policy that gives this account the Read permission level.
• Do not configure the default zone to use Anonymous, Basic, Digest, Certificates, or Kerberos authentication (that is, any forms of authentication other than NTLM).
And clarified again in the reference:
• If you want content within the Web application to be included in search results, ensure that at least one zone is configured to use NTLM authentication. NTLM authentication is required by the index component to crawl content. Do not create a dedicated zone for the index component unless necessary.