Is each user's index stored somewhere in their browser or on your servers? It would probably ease peoples' minds if they knew their history was stored locally, but I can see the performance hit that might make.