I experienced the same problema and i FIXED it!! after chatting with Microsoft technical service many times, the solution give was: format your PC and reinstall Windows..
However, thanks to Gary and his clue... i fixed and this is my solution (it Works for me now)
I renamed (you can try to delete, but i always like to rename to have an easy way to restore) the key
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Search\FileChangeClientConfigs{A010C594-BAB6-4690-952C-28A0C0365307} value=ScopeToMonitor
renamed to
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Search\FileChangeClientConfigBAK{A010C594-BAB6-4690-952C-28A0C0365307} value=ScopeToMonitor
and then started the Windows search sercvice (services.msc).. and right now its working. Its already indexing my files!!
The Windows search service automatically created a new entre in the registry named:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Search\FileChangeClientConfigs
I rebooted my laptop and the service started automatically and its working and indexing!!
Hope this patch helps!
Sergio