All, we have created a hotfix that does two things:
1. After failing to logon as a batch job, the job will immediately retry using interactive logon (pre-U3a way) before failing completely.
2. Warning about backupset update failure was changed to info event which additionally explains the issue in better details:Transaction logs backup will not be possible due to insufficient permissions to update backupset for SQL instance: %SQLInstance%
Adjusting account's security rights and permissions on msdb
according to the updated system requirements
remains the preferred solution for obvious reasons, however we still decided to provide the hotfix for situation when adjusting account settings is not possible. The hotfix is available through our support.