I have had this same problem since probably 3.0. It is sporadic, where some posts make it and some don't. I have 3 subdomains with their own wordpress themes sharing the same database (this is continued from a long time ago - pre the networking wordpress instances, which I use for another batch of blogs). It is sporadic in all 3 blogs (though it seems like 1 will do much better for awhile, then it switches to another doing well...).
WordPress knows it "missed the schedule" because it highlights all that have missed the schedule. There is a plugin that attempts to catch any in that state and then publish them. I think I will try that now. I figured if I just waited a couple versions the bugs would be worked out but that hasn't worked.
I use almost no plugins. I do use: akismet and super cache.