With the following request:

db.tasks.find({status: {$in: ["queued", "running"]},
  reserved: {$lt: now},
  type: {$in: ["most-common-type"]},
  tried: {$lt: 5},
  ns: "default"}).sort({priority: -1, _id: 1}).limit(1)

And one of the following indexes:

db.tasks.ensureIndex({priority: -1, _id: 1, ns:1, status: 1, type: 1, reserved: 1, tried: 1})
db.tasks.ensureIndex({ns: 1, priority: -1, _id: 1, status: 1})
db.tasks.ensureIndex({ns: 1, priority: -1, _id: 1})
db.tasks.ensureIndex({priority: -1, _id: 1})

MongoDB is never using the index, always using BasicCursor and a scan and order to get the appropriate result. The dataset is about 5 millions entries. The find() alone would return about 2 millions entries. The ns field is not very selective ("default" is 9 out of 10).

Another oddity that may be related is the fact that despite not using an index, MongoDB is able to not scan the whole dataset to get a result (nscannedObjects may be equal to 2 millions instead of 5).

Without index, MongoDB is able to answer the request in about 10s. By hinting the last specified index, I am able to get an answer in 3s and no scan and order.