The fix came from the MSDN forums here:
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1214407&SiteID=1
Specifically:
Try to rebuild the index when you have WDS installed. If that doesn't
solve it the do these steps:
1. Stop Indexing service "cmd: net stop wsearch" and check in
TaskManager's process list that SearchIndexer.exe was really stopped.
2. Delete %SystemDrive%\ProgramData\Microsoft\Search\Data
\Applications\Windows (Vista) or %AllUsersProfile%\Application Data
\Microsoft\Search\Data\Applications\Windows (XP) folder with all its
files and subfolders.
3. Delete the following registry keys:
- "HKLM\Software\Microsoft\Windows Search\Applications\windows"
- "HKLM\Software\Microsoft\Windows Search\CatalogName\windows"
- "HKLM\Software\Microsoft\Windows Search\Databases\windows"
- "HKLM\Software\Microsoft\Windows Search\Gather\windows"
- "HKLM\Software\Microsoft\Windows Search\Gathering manager
\Applications\windows"
- "HKLM\Software\Microsoft\Windows Search\UsnNotifier\windows"
You'll have to change reg key ownership and change permission
first.
4. In registry in key "HKLM\Software\Microsoft\Windows Search"
switch "SetupCompletedSuccessfully" subkey to "0" - you'll have to
change reg key ownership and change permission first.
5. Start Indexing service back "cmd: net start wsearch"
6. Wait until "SetupCompletedSuccessfully" subkey switch back to 1.
If it's still "0" after 5 minutes, it means the setup is failed again.