If you find that the ‘reset index’ in the search administrator doesn’t work please try the following:

On all SharePoint Servers run:
1. STOP SERVICES
Stop the Timer service. To do this, follow these steps:
Click Start, point to Administrative Tools, and then click Services.
Right-click Windows SharePoint Services Timer, and then click Stop.
Close the Services console.
Run from the command prompt:
stsadm -o osearch -action stop
iisreset /STOP

2. CLEAR TIMER JOB CACHE
In Windows Explorer, locate and then double-click the following folder:
Drive:Documents and SettingsAll UsersApplication DataMicrosoftSharePointConfigGUID
Notes
The Drive placeholder specifies the letter of the drive on which Windows is installed. By default, Windows is installed on drive C.
The GUID placeholder specifies the GUID folder.
The Application Data folder may be hidden. To view the hidden folder, follow these steps:
On the Tools menu, click Folder Options.
Click the View tab.
In the Advanced settings list, click Show hidden files and folders under Hidden files and folders, and then click OK.
In Windows Server 2008, the configuration cache is in the following location:
Drive:ProgramDataMicrosoftSharePointConfigGUID
Back up the Cache.ini file.
Delete all the XML configuration files in the GUID folder. Do this so that you can verify that the GUID folder is replaced by new XML configuration files when the cache is rebuilt.
Note When you empty the configuration cache in the GUID folder, make sure that you do not delete the GUID folder and the Cache.ini file that is located in the GUID folder.

3. CACHE.ini
Double-click the Cache.ini file.
On the Edit menu, click Select All.
On the Edit menu, click Delete.
Type 1, and then click Save on the File menu.
On the File menu, click Exit.

4. INDEX RESET
Delete Indexquery files on on servers:
c:Program FilesMicrosoft Office Servers12.0DataApplications{GUID}

5. START SERVICES
Start the Timer service. To do this, follow these steps:
Click Start, point to Administrative Tools, and then click Services.
Right-click Windows SharePoint Services Timer, and then click Start.
CLose
Run from the command prompt:
stsadm -o osearch -action start
iisreset /START
Confirm that the IIS Services have all started:
iisreset /STATUS

Start full content Crawls and then incremental Crawls

Confirm that they successfully run