I had a Time Capsule. It had the same issue with Time Machine rejecting the backup and requiring a re-do every year or so. (the Time Capsule ran NetBSD, I wonder what they used for a AFB/SMB stack. Did they port the macOS one over or use Netatalk/Samba?)
Time Machine over a network has always been unreliable.