Take your locally saved copy and try re-indexing the fields.
This is easier to do in FileMaker 11, but since you have 10...
Open Manage | Database | Fields, select a field used in the search that bogs down, change it's storage options to turn off indexing, Leave Manage | Database, then return and turn indexing back on. This rebuilds the index for one field. The challenge is that any one of several fields in your file might have a damaged index.
If you want to re-index all your fields, save a copy with the clone option, and then import all your data into the clone. This will rebuild the indexes of all your fields during the import.