Why are my MongoDB queries really, really slow?

It seems that you are missing an important index, especially since the query with no matches is taking that much longer than a query with matches. What type of query is it? Maybe you need a compound index? Are you using where as part of the query?

I'm not an expert in MongoDB, but 80-90 minutes is absolutely abnormal. I don't know what MongoDB "sounds like" to Arenstar, but it has been shown to handle billions of documents (terabytes of data).

This might be too late for an answer, but I thought it was worth mentioning. There are tools like mongostat that can be used to see what actually is going on. Too many index misses, too many page faults. If you are running simultaneous read and write operations, then you should also look for lock percentage. 300 GB is not a huge amount for mongodb to handle. It can easily go much beyond that.

Other helpful commands:

    db.stats();
    db.currentOp();