I want just going to post about the categories issue but I guess it's exactly the same as you describe it. Here is what I have :
Let's say I have two Categories : Internet Marketing , Affiliates and I have a post called CPA which is added to both categories.
If I searched for :
- Internet Marketing : I get all the posts under this catrgory
- Affiliates Internet Marketing : I get nothing
- CPA Affiliates : I get nothing
- CPA Internet Marketing : I get nothing
- CPA : I get the post
Summary: If I searched for categories (one or two words) I find all posts under them but if I searched for anything combined with category name I get nothing which means Categories are not included in the search even if I set their settings to "Yes"