Based on my reading, under some circumstances the scheduler wasn't dedicating large enough chunks of time to a particular boot process for it actually make progress. The fix appears to have been to change how the time chunk size was calculated.