The Failed Backups
You check up on things, as you usually do, and suddenly find this splendid Windows Backup situation on your Windows Server 2012 R2 server. Forty Million failed backups and counting. What if you had just logged in to restore something for someone? Lets rather not dwell on the what ifs, and rather fix the situation.
After further investigation
You realize that the backup problem is being caused by a space problem. But, you ask yourself as you usually do, is Windows not suppose to automatically rotate old backups out, thereby clearing space?
Is yes. However, Windows Backup can run into issues. Read more about that here. In short, Windows Backup can run into a allocation problem for Volume Shadow Copy Service (VSS). Believe it or not, but Windows is actually trying to prevent the deletion of all your backups to benefit the newest one only. Whilst all this is very interesting, it is actually not really mandatory to understand for the fix.
To remedy the issue, right click your C drive, Properties, Shadow Copies. Now select the backup volume and set limit for shadow copy size (instead of using the default "No Limit"). My suggestion would be 50% of the allotted space you are using for your backups. Now go back to Windows Backup and run your backup manually and Done and Done.