Rebuild the index. Let the indexing process run overnight so by the next day most of the files will be indexed. If it still does not complete the indexing , try to put away the receipt of new emails until indexing is finished.
To rebuild indexing : [
http://support.microsoft.com/kb/932989]
1. Click Start button, click Control Panel, and then click System and Maintenance.
2. Click Indexing Options, and then click Advanced.
If you are prompted for an administrator password or confirmation, type your password or click Continue.
3. Click Rebuild. When you are prompted to confirm that you want to rebuild the index, click OK.
Rebuilding the index may take some time to finish. During the rebuild operation, the indexer tries to reinsert all items into the index.