What makes a perfect signature? Optimal signatures should be consistent within individuals and distinctive between individuals. In defense against avian brood parasitism, some host species have evolved "signatures" of identity on their eggs, comprising interindividual variation in color and pattern. Tawny-flanked prinia (Prinia subflava) egg signatures facilitate recognition and rejection of parasitic cuckoo finch (Anomalospiza imberbis) eggs. Here, we show that consistency and distinctiveness of patterns are negatively correlated in prinia eggs, perhaps because non-random, repeatable pattern generation mechanisms increase consistency but limit distinctiveness. We hypothesize that pattern properties which are repeatable within individuals but random between individuals ("invariant properties") allow hosts to circumvent this trade-off. To find invariant properties, we develop a method to quantify entire egg phenotypes from images taken from different perspectives. We find that marking scale (a fine-grained measure of size), but not marking orientation or position, is an invariant property in prinias. Hosts should therefore use differences in marking scale in egg recognition, but instead field experiments show that these differences do not predict rejection of conspecific eggs by prinias. Overall, we show that invariant properties allow consistency and distinctiveness to coexist, yet receiver behavior is not optimally tuned to make use of this information.