The cron jobs weren't running for delaying the schedule. While not necessary, the WP Missed Schedule plugin was being used. After a bit of digging, I noticed this plugin was slightly out of date (the developer apparently took the plugin out of the WP repo so you need to install it from the GitHub repo).
This plugin also requires WP Control as a dependency. This component was missing, so I suspect that in some previous update this got missed causing posts to not get published.
We should look at if we really need this; PHP cron
has come quite a ways since this plugin was needed. This was really a plugin to fix a bug in WordPress 2.5 (and stayed there for a while).