Hi there!
I’ve come across this multiple times and read the replies to you and the OP.
It sounds like, to me, especially if you can’t backup to any external drive, even after reformatting properly, it may be an OS/content issue as you stated.
First:
Are there any connected drives to your Mac(s) that are also set to be backed up? Of course if so, eject, disconnect and try again.
Your suggestion of excluding files or directories from being backed up is also right on, there is one setting to allow/remove by default, which makes it easier, is I believe System files and Apps, that’s a good test. You can add that to be excluded from Time Machine Advanced Preferences, restart and test.
I know you’ve also probably run first aid, etc. which is another good step if all else fails. Otherwise:
IF the first backup completes okay, but the subsequent ones don’t, then I’d try clearing the Time Machine snapshots, restarting and trying again.
You can do this by opening Terminal from Finder > Applications > Utilities. Then run and enter the following command:
sudo tmutil thinlocalsnapshots / 999999999999999 4
(Yes, that’s 15 9’s)
Restart your Mac and try again.
Otherwise, if all else fails, I may delete the Time Machine plist/restart:
Open Finder > Go > Computer > Macintosh HD (Usually) > Preferences.
Save a copy them delete com.apple.timemachine.plist, then delete the file from that location, restart and test again. If you do this, you will have to choose your backup disks again, however if it is an issue with this property list, it may just fix the problem.
You can also use Terminal to check the Time Machine status, it’s not much, but you can run and enter:
tmutil status
And of course, testing the backup process while in Safe Mode or in another active user account is a good test/solution.
Knowing, of course if another Mac has the same issue with the same external drive, or the same Mac has an issue with another external drive would be revealing. Hope something here helps!