When this happens I am sure you will be told to check your permissions here and there, but you are sure you have all needed permissions set perfectly. So you put yourself into google search, still, everybody talks about nothing but permissions.
And -
Here is another important thing to check: to run as a schedule tasks, the credential used must have "Log on as batch job" privilege. This will be added for you automatically when you created jobs, sweet. However, if it is removed later on with whatever reason, or overrided by Group Policy, that is when issue starts.