Surprisingly you might find the problem is actually down to a simple caching issue with a one line code fix. Magento caches it's cron schedule and reads this cached content on subsequent runs of cron rather than recreating the schedule each time to determine which jobs it should execute. The problem is sometimes jobs just don't get cached despite them being configured correctly so when the time comes for them to execute nothing actually happens.
It's worth noting that the cron schedule is cached even if all caching is disabled in admin, and the only way to clear the cached schedule through admin is to Flush Cache Storage under System->Cache Management. Unfortunately this doesn't then cause the jobs to be correctly cached the next time cron is run.
So the fix is to simply disable the caching of the cron schedule, and don't worry, benchmarks with caching disabled shows this to have no negative impact on site performance.
Copy:
app/code/core/Mage/Cron/Model/Observer.phpto:
app/code/local/Mage/Cron/Model/Observer.phpif it's not already there. Open the copied file and find the following line inside the generate() method:
Mage::app()->saveCache(time(), self::CACHE_KEY_LAST_SCHEDULE_GENERATE_AT, array('crontab'), null);This is the line that initiates caching of the cron schedule, so just comment it out:
//Mage::app()->saveCache(time(), self::CACHE_KEY_LAST_SCHEDULE_GENERATE_AT, array('crontab'), null);Save the changes and Flush Cache Storage to clear any currently cached cron jobs and your store should now always execute properly configured cron jobs.