How to feature-ize multiple vocabularies applied to multiple content types?
An important thing to keep in mind is that things start getting messy when multiple features try to export the same thing. For example, have multiple features that export the same Taxonomy vocabulary. When this happens, best case scenario is that you have to update all the features every time you make a change to the vocabulary. Worst case is, well, worse than that. I've heard some horror stories, but never tried it personally; I do my best to keep proper separation.

In your case, I suggest separating the content types and vocabularies into separate Features. For the vocabularies, you can either put them all in one feature or split them up into separate features, whichever you prefer. I tend to keep all the vocabularies in a single feature, which I think makes sense for your situation as well. For the content type Features, you can now list as a dependency the Features module defining the vocabulary used by that content type.