Error: The backup data at the end of "" is incorrectly formatted

Sometimes, your backup jobs or adhoc backup might fail with below error

"The backup data at the end of "" is incorrectly formatted. Backup sets on the media might be damaged and unusable. To determine the backup sets on the media, use RESTORE HEADERONLY. To determine the usability of the backup sets, run RESTORE VERIFYONLY. If all of the backup sets are incomplete, reformat the media using BACKUP WITH FORMAT, which destroys all the backup sets. [SQLSTATE 42000] (Error 3266)  BACKUP DATABASE is terminating abnormally. [SQLSTATE 42000] (Error 3013).

The error itself has solution and the problem. This happens when your backup set is corrupted for some reason and you try to create back to the same set. Corruption for back might have various reason.

The easiest solution to this problem is take backup using BACKUP WITH FORMAT option, which destroys all previous backup sets and create a new one.