"... allowing wild cards would explode the combinations ..."
I don't think wildcards is what Matt needs. From what I understand he just does not want missing values to be counted against the rule.
It's hard to accomplish when the data is represented as a 'transaction', i.e. item counts against the rule if it's not present in the transaction. Hence there is not way to account for missing values.
If data represented in a tablular form:
|Favorite beverage||Car or Truck?||Likes football?|
it should be possible to ignore the missing values. when calculating support, etc.
I don't know existing algorithm that approaches the problem from this angle but I see it's value for sociology, business intelligence, etc.