It seems that the $exists operator does not work on keys which have been indexed. If a key has an index, the $exists operator will never return any documents. I've attached some tests in ruby which demonstrate this, along with their output, and an example mongo console session showing that it's not just an issue with the ruby driver.