If you attempt to start Windows SharePoint Services Search service and receive the following message:

Try modifying the Log On Identity of the service.  In my case, it was setup to log on as "Local Service".  After I changed this to "Local System", the service started without any errors.

Note that this error message was received from the Services Administrative Tool.  The WSS web front-end simply hung when attempting to start the WSS Search service.