I think the issue is this:
Darkside check your "missing" products in a category. I believe you will find that they have not been assigned to the Main Category, like Makeup, but only assigned to a subcategory like Makeup-Checks.
The system does not assume that you want a product assigned to the main Category just be cause it was assigned to a sub-category.
Give this a try and see if it solves your issue.
Lee