1. Navigate to ~Program Files~\Common Files\Microsoft Shared\web server extensions\12\bin.
2. Execute stsadm -o spsearch -action stop
3. Delete your existing search database, e.g. WSS_Search_"your server"
4. Recreate your search database, be carefull to use Latin1_General_CI_AS_KS_WS as collation and your domain account for search service as owner of the DB.
5. Execute stsadm -o spsearch -action start

=> your MOSS 2007 search database will be recreated.