So many times I hear people saying: I had a page, but can't remember what it was.
People could use google, but you could put extra work into brewing up some special sauce that would, for example let them find their sites with only a combination vague memories, such as their neighborhoods, or when they created it, or the types of things they linked to, or the background music their site had (mine had the mission impossible song) or the type of content (mine had lots of animated gifs). Google wouldn't care enough to do that.
If users find their content on their own, they can always request it to be removed, all you're selling them is a tool to help them do it.
I wonder if people would really pay for it? It would be fun to find out. I would help build it
There's a sketch on my notepad here about authenticating 'lost' content. It's not easy and there will be a lot of stuff that needs special casing, but I think it can be done.
Do you still have control of the from address of the posting?
I've deleted stuff from newsgroup archives before, had some hoops to just through, but it was possible.