We've made some changes and think we've determined the issue. We were creating an index per day but were processing documents from many different days (from over several years) in a random order so almost every index request was causing the server to create a new index. It appears that the time to create a new index is very large in comparison to index a document into an existing index. Also, we found the gc was always running and could never free much memory (e.g. freeing 1MB and using 1Gig).
If we create many indexes and are using the default of 5000 for index.translog.flush_threshold, would that cause the server to try to keep everything in memory, thus causing it to slow down considerably?
And our hypothesis is that once it slows down, replicating and/or moving the shard fails silently and then we start getting IndexMissingException.