A method for rewriting track packets that fail a check-after-write test onto a track of a storage medium is presented. Local packet address information is included in the track packet itself to allow track packets to be written to the storage medium in any addressing order. This allows a single packet to be rewritten along a later track among other track packets that are being recorded for the first time, thereby reducing rewrite track overhead and eliminating the requirement for a lengthy backhitching sequence.