WSS 3.0 Search Web Service returning fewer results

It appears that the WSS (Windows Sharepoint Services 3.0) Search Index/Database doesn't update rights/permissions given to new users of documents already indexed.

A colleague presented a strange problem where he was attempting to use the search web service (spsearch.asmx) to search certain terms. He was providing the service, credentials of a site collection administrator because he needed all the search results without any permission restrictions. The site was operational for a few days and the search working fine and then he added a new site collection administrator. This administrator was also a local server administrator on the server where the service was installed (probably doesn't make a difference, but anyway). Strangely, to this new administrator's credentials the search web service was returning results as if the user was a reader.

We looked around the internet not finding any solutions. However, I suddenly remembered something about IFILTERs. If you install an IFILTER (say for PDF) after you have uploaded some 100 pdfs, those 100 pdfs are not indexed ever and the quick and dirty solution was to recreated the index. I just thought this might be a similar situation. The older documents in the index were not updated of the fact that this new user was a site collection administrator with access to those documents. So we did the following to try and solve the issue:

1. Goto Operations in Central Administration
2. Goto Services On Server
3. Stop the WSS Search service. This will delete all the index files
4. Now setup a database by clicking the WSS Search Service link
5. Restart the search service.

It rebuilt the index and this time the search web service was able to receive results uploaded before the new administrator was added.