This problem is resolved for now.
The resolution came in two parts. The first was that I lowered the service_reaper_frequency to 1 from 10 in nagios.cfg. This perhaps allows nagios an easier time of processing data, instead of doing a lot at once. I'm not really sure. In any case, doing this seemed to keep service checks from falling off the queue.
The other setting I made was to enable check_for_orphaned_services in nagios.cfg. This is kind of the back-up plan, and it appears that service checks that were supposed to have been rerun, but didn't run or return results, will be immediately requeued.
Since implementing these changes our service check schedule has been keeping up to date.