How Does Time Machine Check for "Runtime Corruption" and How Do I Reset It?

I've now discovered a complete solution by (carefully) following these steps:

1. Turn off Time Machine's automatic backups in the Time Machine preference pane (to prevent any conflicts).
2. First mount the network volume to which Time Machine is backing up, how to do this will depend upon your system, there should be a disk image in there named after your computer (e.g- for a system named "Haravikk's Mac Mini" you'll find "Haravikk's Mac Mini.sparsebundle"
3. Attach the image using the following command in Terminal.app: hdiutil attach -readwrite -nomount /path/to/image (you can fill in the path by dragging onto a terminal window from the finder, just make sure there's a space after -nomount).
4. Take a note of the device numbers returned, one of these will be your backup volume, usually the last one in the form of diskNs2 where N is the disk number, and the s2 should be the partition.
5. Run the following command, taking note to add r to the start of the device number to connect to the "raw" (unbuffered) device: fsck_hfs -p /dev/rdiskNs2
6. Wait for the check to finish; if it finds any errors it should attempt to fix them then run again automatically, wait for the process to finish. If it reports there were errors that could not be fixed then you should consider discarding the backups as recommended, or else run the command again with -f instead of -p (though this is not recommended).
7. At this point you should really check that your latest backup isn't corrupt; you can do this visually by mounting the image (diskutil mount diskNs2 substituting as appropriate) and examining in the Finder. A more detailed comparison is recommended however but beyond the scope of this answer.
8. Detach the disk image with the following command (substituting disk ID): hdiutil detach diskN (if you mounted the image above, "eject" it first).
9. In the Finder open the the folder with your backup disk image, right-click it and choose "Show Contents". Inside you'll find a file called com.apple.TimeMachine.MachineID.plist, open it. If you have Xcode installed it will open in this, otherwise you should be able to open it in TextEdit; when editing in TextEdit you'll need to have some familiarity with XML and plist files, though they're pretty straightforward.
10. Find the VerificationState key and change its value to 1 (it will probably be set to 2 if you're experiencing the same issue as me).
11. Find the RecoveryBackupDeclinedDate key and delete it, if you're using TextEdit make sure you also delete its <date> value.
12. Save your changes, unmount the network volume and re-enable Time Machine's automatic backups.
13. Either wait for the next backup, or run one immediately; if your network destination isn't your only backup device you can trigger a backup to it in the Time Machine preference pane by right-clicking on the destination's icon and choosing "Back up to now".

Details

It seems that Time Machine's "runtime corruption" check is a call to a fsck_hfs -q, which checks whether a volume was unmounted uncleanly. If this fails, the volume will have an "inconsistent" bit set against it that can only be cleared by successfully repairing it using fsck_hfs -p or similar.

However, in addition to this Time Machine stores a "corrupt" status in its com.apple.TimeMachine.MachineID.plist within the disk image bundle. I'm kicking myself for not finding this sooner since it's right there just inside it. I'm not sure if Time Machine performs any additional checks, there is a key related to some kind of extended check, but I'm not sure exactly what this entails.

Correcting both restores the image to "normal" status, allowing Time Machine to run without issue.

NOTE: While in my case the "runtime corruption" check was definitely mistaken, it is important that you check whether there is any actual corruption to ensure this is the case. It's a bit beyond the scope of this answer to cover that as well, but if anyone would like to recommend tools or guides for doing so please comment!

Extra

I ended up finding these solutions myself despite trying to get help from Apple engineers; they just wasted my time trying to find ways to blame me for the fault, rather than telling me what I needed to know, and they've gone and closed my bug report despite my having shown them exactly how I verified no corruption had occurred!

Very, very disappointed with Apple's handling of a report that their flagship backup tool may be deleting users' backups unnecessarily. I'm now seriously considering ditching Time Machine entirely next time I upgrade my storage, as I'm no longer confident I can trust it, or the engineers who work on it, and may go for the overkill option of something based on ZFS send.

After following the instructions, I wasn't able to run fsck_hfs because I lacked permissions, even as root. The fsck only ran after changing the sparsebundle's permissions and mounting it with readwrite access

chflags -R nouchg /Volumes/xyz.sparsebundle
hdiutil attach -nomount -readwrite /Volumes/xyz.sparsebundle