It turns out that guessing what MySQL is going to do in extreme cases is actually pretty hard. Actually there is a followup commit to this one where Dre and I figured out that you can just use FORCE INDEX to get better behavior.

Without the forced index, MySQL was pulling out every single row for the journal and filtering to figure out which ones weren't deleted or suspended. Talk about inefficient! :(