macOS Tahoe is absolutely the culprit. It messed up my almost three years of backups. After upgrade to Tahoe, TimeMachine started giving "disk full error" message even though it had consumed all the disk capacity.
Starting backups afresh on a freshly formatted disk did not help. Same error message. In frustration I ended up calling Apple Support. After about a month, of several screen sharing sessions, the following steps are showing promising signs of working again.
The fix at least for me involves starting backups afresh. So you will lose all your older Time Machine backup history.
The fix was to delete some backup related settings via the command line.
The commands to enter in a Terminal shell are:
sudo xattr -d com.apple.timemachine.private.structure.metadata /System/Volumes/Data
sudo xattr -d com.apple.backupd.ModelID /System/Volumes/Data
sudo xattr -d com.apple.backupd.HostUUID /System/Volumes/Data
sudo xattr -d com.apple.backupd.ComputerName /System/Volumes/Data
sudo xattr -d com.apple.backupd.BackupMachineAddress /System/Volumes/Data
After all this if
sudo xattr -l /System/Volumes/Data
returns
purgeable-drecs-fixed:
and nothing else, then in theory that is all you have to clean up before resuming Time Machine backup again.
Your macOS machine may not have all these values defined. So just ignore if the command throws an error or warning. I was too tired to challenge and optimize. I just ran the commands blindly.
After this, I reformatted the Time Machine backup disk and restarted the backup. It has been 24 hours and it has not thrown an error. So I decided to share what I had learned here early.
If I encounter failures again, I will post again. Try these steps and see if it works for you. Hope this helps you recover too. I am feeling somewhat relieved now knowing that I have a good backup again now.
I am thankful to Apple Support to help me recover.