Methods and apparatus for determining increasing robustness of media signatures are disclosed. An example apparatus includes a characteristic analyzer to determine a first difference between (A) a first characteristic of an audio signal at a first time and (B) a second characteristic of the audio signal at a second time. The apparatus further includes a characteristic enhancer to compare the first difference to a first threshold; at least one of (A) boost the first characteristic of the audio signal at the first time or (B) attenuate the second characteristic of the audio signal at the second time when the first difference does not satisfy the threshold to create an enhanced audio signal; and determine whether a second difference between a third characteristic of the enhanced audio signal at the first time and a fourth characteristic of the enhanced audio signal at the second time satisfies the threshold, the third characteristic corresponding to the first characteristic, the fourth characteristic corresponding to the second characteristic.