realmaverick - 1:37 pm on Jun 14, 2012 (gmt 0)
404 means the page is missing. Often Google keeps the page in the index for some time. So from a UI perspective, I'd still have the related products. Just ensure they are related, a random selection won't be very helpful to the user.
410 means gone but in my experience, Google treat 410 and 404 pretty much the same.