i would ask what is the influence of the soft 404 and how google handle this pages ?
cause the data feeds are highly dynamic some brands get imported and other which been indexed are not any more avaliable so the webmastertool will spit soft 404 page errors.
With the ever changing datafeeds there is indeed a problem with a lot of categories appearing and disappearing.
There are basicly to options redirect to a different page with some results or stay on the page and send a 404. But what to display on the later?
I actually tested using 404's results in a message from google as well, similair to the soft-404 message.
I have no idea what the best solution would be regarding google, well think the soft-404 pages are a minor problem compared to the low-quality duplicate content issues you are facing using datafeeds :
affiliatefeeds.nl/other/1251-google-your-site-sucks.html
Well a solution is adressing the soft-404's and other issues :
write an article for each product category you want to display, add a module showing the product. Even if there are no products to show there is still a page.....
the problem will start with brands and colors cause i have more than 500 brands in the site and they have no own content only some general wrote things for a produkt search machine..