I just finished a strange troubleshooting session. While attempting to start the WSS Search Service the process would create the database and then error out with "File not found". There was a bit on information in the Event Log, but it all pointed to "File not found".

I finally tried to launch regedit.exe and received the message:

"Registry editing has been disabled by the administrator."

Turns out there was a group policy in effect that limited the rights of the service account. We removed the restriction and everything started properly.