Seu explain() saídas sugerem que:

1. 
   Existem 10962 objetos que possuem key.a : 456213154 . Seu db.collection.find({"key.a": 456213154}) consulta usou o índice em key.a , e retornou 10962 objetos.
   
2. 
   Existem 0 objetos em sua coleção que possuem key.a : 456213154 e tem key.b : { $exists : true } . O db.collection.find({"key": {"a": 456213154, "b": {"$exists":true}}}) query usou seu índice na chave.
   

Veja o n valor para cada consulta - este é o número retornado; e o cursor valor - este é BtreeCursor se um índice for usado. Nesse caso, faria sentido por que a primeira consulta demora muito mais, porque tem muito mais objetos para retornar.

Tem certeza de que os documentos com key.a : 456213154 valores também têm key.b valores?

Editar:

A consulta com o $exists param é a sintaxe errada para verificar a existência em documentos incorporados.

Tente db.collection.find({ "key.a" : 456213154, "key.b" : { "$exists" : true } }) .