It sounds like the content got removed completely, so there should not be a URL (either old or new) for that content.
It's true that they should have used 301s or rel=canonical or something in the past, but that also sounds like the least of their past problems, if I'm reading the parent comment right. Right now, I don't think they'd be much better off with 301s to a single URI that 410s instead of just directly serving 404s for everything, even though the 301 to a 410 is more right in some abstract sense.
http://www.w3.org/Provider/Style/URI.html
> Actually most of those 100 are the same few pages
You could redirect them all to the canonical location for those pages.