First of all, automatic labeling based on keywords/conditions is only available in the premium E5 SKU. Other than that, check if any of the locations in which those items are stored (mailboxes, sites, etc) is not put on any type of hold.
Not sure who exactly needs the E5 licenses, as labeling is supposed to happen automatically after all. But there need to be at least some E5 licenses available in the tenant. To get a proper answer, best open a support case.