Hard to diagnose from a distance. However, if it is only happening to a few orders then you need to identify what is different to other orders where it works correctly.
A few questions I would be asking are:
Are these orders all on a common strategy?
Do the orders meet the selection criteria for the normal deadline monitoring variant or are they only then being picked up by one run to pick up all the rest?
I am not sure what you mean by compliance categories in a task list - Do you have more information on this and how your company have configured it?
Normal Early Start and Early Finish tolerances in a maintenance plan calculate from the shortest package in a strategy. This may be shorter than the shortest package used by an individual maintenance. I have often seen users confused by this.