although i voted to move to serverfault, here's my 2 cents:
use the following command in a command window (of course in the C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\BIN folder):
first, trigger a (re)install of the services using:
psconfig -cmd services -install
Now start the wss search service using:
stsadm -o spsearch -action start -farmperformancelevel "PartlyReduced" -farmserviceaccount "WSSSEARCH_ACCOUNT" -farmservicepassword "WSSSEARCH_ACCOUNT_PW" -farmcontentaccessaccount "WSSCONTENT_ACCOUNT" -farmcontentaccesspassword "WSSCONTENT_ACCOUNT_PW" -indexlocation "DIRECTORYPATH_TO_INDEX" -databaseserver "DB_SERVER_NAME" -databasename "DB_NAME"
where you replace all the stuff i capitalized here with your own information.