I tested the behavior and I was able to get products to show up for subcategories and search works when there is a product in the subcategory. Adding a product to a subcategory doesn't add it to the category. You will have to add it to both the category and the subcategory for it to show up in both.
What browser are you using to perform the searches? Are you accessing the categories and subcategories through the sidemenu or the top menu?