While installing WSS 3.0, I came across another strange error when I try to start my Search Service in the server farm. For some reason WSS refuses to acknowledge that the machine is the indexer. The setup was on single a 64 bit machine installed as a server farm. After reinstalling and re-confirming that everything is where it should be, I decided to try the most unlikely reason why it fails.
I used the server name instead of its IP address when specifying the configuration. Strange enough, WSS stops denying the search service.