TheMadScientist - 1:36 pm on Nov 11, 2012 (gmt 0)
My guess is a 301 would not make a difference here, since the difference between a 302 and 301 is mostly semantic these days, especially since time is a definite factor in redirects with Google and this one has been in place for quite a while.
I'm not 100% sure, but my suspicion, since you say the products you have change over time, is you redirected the page from where it was to where it is and for the period of time the redirect was put in place through 'no soft 404' notice, the content of the new page was similar enough to the original to be considered equivalent, but has now changed enough to be considered a 'different page', so it's treated as a soft 404.
See if I can explain what I'm thinking a bit better:
You originally redirected the page to an equivalent.
Google doesn't like to 'throw anything away', so they compare the original you redirected to the page you're redirecting to for similarity.
Over time the products on the page you're redirecting to have changed.
Recently, one of those changes hit a 'threshold' so the page on the receiving end of the redirect has become enough different to be considered a 'different page' rather than an 'essentially the same' page.
Now you get a 'soft 404' error notice.
A 410 is definitely not the right answer IMO since you still have the page and it is an equivalent even though Google's 'not getting it', because you lose all the history, age, link weight, etc. of the original page if you 410 it.
A 301 probably won't make any difference, because it's not an 'essentially the same' page according to an algo any more, so any comparison of the original to the new page will have the same effect, regardless of status code.
What is the right answer? I'll have to think about that for a bit and I'll post again if I think of something other than 'ignore it', because it's wrong on their end, not yours.