Windows search is not started

If you right click on the Windows Search in services.msc and select Properties and under the Dependencies, you will see that it relies on Remote Procedure Call service being started.

Scroll back up through services.msc and ensure that this service is set to Automatic and Started - its the one with the Description RPCSS.

This is for Vista but the same route works in Win 7 to rebuild the Index How to Fix Microsoft Windows Search Indexer Stopped Working and Was Closed

Have you checked Event Viewer for any related Errors - if you find any, then click on the blue Online Help link and that should provide you with a solution if the above rebuild link doesn't do it.

Have you tried restoring back to a point prior to this problem and did anything show up in Event Viewer ?

I'm not sure if Last Known Good Configuration would cover this, but boot up while tapping F8 and select that option - which can be a quicker way than manually searching through the restore points and scanning for affected programs.

Had you downloaded anything prior to this occurring or have you been using any 3rd party Tune-up programs ?

When you access Indexing Options, at the bottom of the opening window is a blue link for Troublshoot search and indexing - did you try that ?