Isn't part of that problem how you define a "characteristic" (and thus, the combinations of them)? Because if it has k-anonymity for a certain set of characteristics, but you invent a new characteristic (based from combining info, datamining and perhaps other sources), the property doesn't necessarily hold any more.