I had the same problem except that one database out of job with 12 restores and multiple other jobs with a total around 250 restores would fail.

While the job is owned by SA (helps avoids windows authentication issues) the Service account was a login on the server but not part of the SysAdmin role except through Administrators group permission.

I gave the service account SysAdmin role, and hopefully this will work from now on.