After more digging, I've found out that its not 4 attributes thats my upper limit, its more randomly than that.
Adding/removing attribute values from a product change if the filter for that particular filter works or not.
An example. A product has 6 attributes with in total 15 attribute values. The filter on attribute "stock" does not work.
I remove one attribute value from one of the other attributes, for instance a color.
Now the filter on attribute "stock" works just fine.
It doesnt matter what attribute value I remove, so its not just one attribute or value which causes this... hmmmmmmm.....

suggestions?