It appears that when disconnecting from a network while a TM backup is in progress results in the "Time Machine has completed a verification of your backups" message once the connection to the backup server has been reestablished.
This has recently occurred five times in a row as my computer has had to move around between my home and school quite a fair bit in the past few days and will likely continue doing that for the rest of the year. I would let it complete the backup overnight, go to school in the morning and be greeted by the dialog when I return home to the network that the backup is on, let it run overnight again, and the cycle repeats.
Is there any way to avoid/resolve this matter besides having to do the steps in http://www.garth.org/archives/2011,08,27,169,fix-time-machine-sparsebundle-nas-based-backup-errors.html every time this happens? It's fairly annoying because I have a backdated 100baseTX network which means transfers in the order of gigabytes can take six, seven or even eight hours.
edit: version information and more
Computer OS X El Capitan 10.11.4 (but this issue has been happening since and possibly before Mavericks) Mid-2014 13" rMBP@3.0GHz, 16GB RAM
Backup server and network NAS running Debian with AFP support and sparsebundle file over a 100 Mbit connection
I highly suspect that this perpetual verification is caused by network intermittency - for some reason disconnecting during a backup causes TM to have to verify the backup and once reconnected, declare it "corrupted".