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.