A gift with purchase does not appear on some orders but works on others.

Check three things in this order. First, that the specific conditions of the discount rule are actually met. That includes if the rule is stackable. Second, whether another rule with higher precedence applied to that order instead. Third, whether the specific product variant is in stock and have a price for the specific sales channel (store group) and country (store market).