Yep, and after doing all of that I still couldn't delete the backup. I tried deleting it from the iPhone iCloud UI as well as the iCloud settings UI on the Mac.

Yep, and after doing all of that I still couldn't delete the backup. I tried deleting it from the iPhone iCloud UI as well as the iCloud settings UI on the Mac. Neither option actually deleted the backup. For giggles I tried to dig around in the iCloud drive app but that doesn't expose anything. The Web UI is equally useless. It would be nice to have a button that just "resets all iCloud storage" but that doesn't exist either. I did find a workaround. Back up phone manually (in iTunes), wipe phone, restore the (months old) iCloud backup. I was able to delete the "newer" iCloud backup after that. I then restored my backup from the computer and the iCloud backup mysteriously started working again (registered as a single backup for my phone instead of two). This was all over a year ago, so maybe they fixed it since then. The other phone on another account still won't back up to iCloud. The backup size is a fraction of the "free space" on that iCloud account and the error message is still the cryptic "failed to back up" message.