A "legitimate" signature (or, for a better word, a good-performing signature) is one that performs well on both precision and recall ( https://en.wikipedia.org/wiki/Precision_and_recall ).

Precision is the ratio between correctly-identified cheaters and the total number of people matched by the signature.

Recall is the ratio between correctly-identified cheaters and the total number of cheaters in the system.

In this case, the signature had good recall but poor precision, as those threads describe cases that make it plausible to have a "catbot*" username without cheating.

(I said "had" because the recall rate is going to drop when the string gets changed by the cheat authors. So long-term, the signature is poor on both recall and precision.)

The most problematic issue I see for Valve is not the lack of measurement of precision and recall for their VAC ban signatures, but rather the inability to obsess over their customer experience and react properly when relevant issues in their products are reported.