Thanks for the answer.
The DBCC Task executes for a little more than 3 hours, then it moves on to the Backup task. It will execute for roughly 7 minutes and stop, report success and move on. The order for which it is backing up is by name, so it is stopping on the master database. This is consistent on all servers that have long running DBCC tasks. This is really strange.
We have tested another configuration by disabling the DBCC task and ran the Backup task without issues. It performs all backups without problems. This is why we were baffled and thought that there might be some hidden timeout.