I was getting some issues with Time Machine, where, after backing up, it would always attempt a verification, and then complain that the verification was incomplete. These messages were only visible in the system log—there was no alert popped up.

Sep  9 08:37:30 XXXXX.local com.apple.backupd[72558]: Verifying backup disk image.
Sep  9 08:37:34 XXXXX.local com.apple.backupd[72558]: Backup verification incomplete!

The backup is to an OS X Server, and the TM backup is kept in a disk image, called Machine-Name.sparsebundle.

I thought that I would manually verify the backup and opened up Disk Utility. There I noticed that the Machine-Name.sparesebundle was already in the sidebar, even though the remove volume was not mounted. I then noticed that the path to the volume was

/Root Volume Name/private/var/db/com.apple.backupd.backupverification/Machine-Name.sparsebundle

Aha!

Closer investigation showed that /private/var/db/com.apple.backupd.backupverification contained a slightly modified copy of an out of date version of the Time Machine disk image.

% sudo ls -lhFG /private/var/db/com.apple.backupd.backupVerification/Machine-Name.sparsebundle/
total 24
-rw-r--r--  1 root  wheel    11B  5 Jul 22:18 HC.progress.txt
-rw-r--r--  1 root  wheel   500B  5 Jul 22:15 Info.bckup
-rw-r--r--  1 root  wheel   500B  5 Jul 22:15 Info.plist
drwxr-xr-x  3 root  wheel   102B  5 Jul 23:49 bands/
-rw-r--r--  1 root  wheel     0B  5 Jul 22:15 token

Looking closely at this revealed that the disk image was corrupted, so I simply removed it

% sudo rm -rf /private/var/db/com.apple.backupd.backupVerification/Machine-Name.sparsebundle

and then did a manual verification (hold down option while selecting the Time Machine menu and choose Verify Backups). When the verification finished (successfully), the directory was left empty.

So, in summary, if you end up with the “Backup verification incomplete!” message, try deleting the /private/var/db/com.apple.backupd.backupverification/Machine-Name.sparsebundle and see if that fixes it.