Cart Price Rule based on category does not work via Rest API

Question

I have created a Cart Price rule (not catalog) and applied a discount to it. I can apply the discount fine using the store's UI. I can also apply the discount via Rest API. Then if I add an action to only allow the discount if the product belongs to a category I can still apply the discount via store's UI but when I try via Rest I get the response that the discount code is not valid. The Rest request is made through another store view but the category is also visible in said store view. What am I missing?