You'll do well to draw out a tree of what you're after to make sure you really understand for yourself what you want.
Yes, you'll likely need to put each product into multiple categories to achieve this. VP-ASP does not allow sub-categories to appear in multiple categories. You'll just build the entire tree of categories and sub-categories so that it represents each way that you want customers to be able to click through to your products. Each manufacturer may need to be under multiple product categories, and each product type may need to be under multiple manufactures to get what you describe. I'm not sure exactly what you are after, but it sounds like you may need 32 different sub-categories: one for each combination of 4 product types and 4 manufacturers times 2 different ways to get to them. This can get pretty complicated. Realize that if it is complicated to lay out, it might also be complicated for your customers. Do you really need all these different ways to get to your products?
Once you have mapped out and created all your categories, add each product to each of the relevant categories and sub-categories. To add a product to multiple categories, hold down the <Ctrl> key while selecting multiple catgories and sub-categories in the edit product entry page under shop administration. Both the category and the sub-category have to be selected in order for the product to display correctly.
Notice below that PRODUCT X shows up in multiple categories and sub-categories:
ManufacturerA
|-ProductTypeA1
|-ProductTypeA2
|- PRODUCT X
|-ProductTypeA3
|-ProductTypeA4
ManufacturerB
|-ProductTypeB1
|-ProductTypeB2
|-ProductTypeB3
|-ProductTypeB4
ManufacturerC
ManufacturerD
ProductCategory1
|-ManufacturerA1
|-ManufacturerB1
|-ManufacturerC1
|-ManufacturerD1
ProductCategory2
|-ManufacturerA2
|-ManufacturerB2
|- PRODUCT X
|-ManufacturerC2
|-ManufacturerD2
ProductCategory3
ProductCategory4
We should probably lobby VP-ASP support to modify the product to allow sub-categories to be associated with multiple categories as this would simplify things a lot. However, I think this may be a major change to the design of the cart.