Inconsistent Search Results with 2 Node Cluster

We are using elastic search. We have a 2 Node Cluster with 2 shards and 1 replica and are indexing around 4 million documents. We started noticing that the search results that we are getting back from the cluster are inconsistent in the total number of counts for the results, as well as the results that are being brought back.

Here is an example:

I search for a document with a very unique name using a DSF_QUERY_THEN_FETCH search. I know there is only one of this document on this server so when I search for the unique name, I should get only one document back but when I search it multiple times here is what happens (I excited the same search 5 times in a row)

Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 0
Search “uniqueTerm” Results - 0
Search “uniqueTerm” Results - 0

And then it repeats the exact same pattern. It’s like it’s not finding the data part of the time. The weird thing is that it doesn’t matter have fast or how slow the I excite the searches, it finds it the first 2 times and for the next three it doesn’t.

HOWEVER:
If I modify the cluster to have 1 node, 1 shard, no replicas, and repeat the same test the results are such:
Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 1
Search “uniqueTerm” Results - 1

We are running elasticsearch 1.1.0 and using the Java API to excute our searches.

Does anyone know if there is a setting or something that we are missing in our cluster?

EDIT: We have 2 nodes and each live on their own seperate linux server.

Thanks again