Windows 7 Windows Search Not Working

In "Turn Windows Features On or Off" (Control Panel > Programs and Features) is Windows Search ticked?

In Regedit, navigate to this key HKEY_LOCAL_MACHINE***\Software\Microsoft\Windows\CurrentVersion\Explorer\FolderTypes\{EF87B4CB-F2CE-4785-8658-4CA6C63E38C6}\TopViews\{00000000-0000-0000-0000-000000000000}
In the right hand window check that the GroupBy string value data is System.StartMenu.Group

***This may also be under HKEY_CURRENT_USER

Also if you have a 64 bit system check this key as well HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\Windows\CurrentVersion\explorer\FolderTypes\{ef87b4cb-f2ce-4785-8658-4ca6c63e38c6}\TopViews\{00000000-0000-0000-0000-000000000000}