One issue I've noticed in the past: If for some reason the *previous* cron job is considered "still running", it appears the cron service will not trigger a new request. We've occasionally seen issues where a request on a backend service gets "stuck" and runs for an extremely long time (usually due to some sort of bug). This can prevent the next cron from running. One disgusting hack that we've used to recover from this scenario is to forcibly stop the version that is running and start it again, to force any "stuck" requests to be terminated.
We've also seen similar failures for task queues with low "concurrency" limits. For example, if the limit is 10 concurrent requests, and they are all "stuck", no more tasks will execute.
I'm not sure this is what you are seeing, but I'm mentioning it in case it is helpful to track down your issue. Good luck!
Evan