I don't think this is an easy one, but the time and resources required to re-index a large number of changes are quite significant.
Is it possible for a re-index to index a configurable number of files on each invocation? This would leave the repository search out of date, but release the server to serve the requests of other users. Susbsequent re-indexes could fill in the gap.
I'm not sure how valuable this would be if #365 were implemented, as one huge cost to re-indexing (tagging and branching) could be radically reduced.
Nonetheless, repository search is transparently such a great feature is would be a shame if it became a victim of its own success when people with large-ish source trees (>1K files) have a go at using it.