We used to have this problem in my org too until I realized that some of the users who were having problems with the OOO agent, their template was signed by an admin who had left the company and hence was not in the NAB.
One way to resolve this is by signing all the agents in all templates that you have in your org. with a secured ID. Preferably this ID should not be a person but one that you use to sign agents, deploy apps and has all the necessary access and also listed in the ECL.