Presumably, if society is willing to let people return it must gain from their return. That cost benefit trade-off is the exact same one that occurs with your website example.
I agree our society does not treat ex-convicts well. But changing that requires a cultural shift, not a legal one. We should work on getting people to humanize ex-convicts, not legally trying to make them forget they are ex-convicts.
However, the 1st amendment to the US Constitution puts strong limitations on the ability of the government to prevent or censor expression. How can the worthy goal of improving convicts' rehabilitation--albeit via suppressing news and opinion--possibly square with free speech?
Or what about bad yelp reviews? If you exterminate the cockroaches, can you delete all the bad reviews?
But, to reiterate the point: that does not proof that all such hypotheticals are undecidable.
Imagine someone stealing 1 cent. Should they go to prison? Of course not! Now imagine them stealing 100 million cents, i. e. $1 million. Should they go to prison? Of course!
Just because we're both going to have hard time saying which single cent of those 100 million made the difference between something to ignore and something to punish does in way mean theft should be legalised.
And yes, changes in efficiency do matter. That's why even the US does not recognize a right to privately build, own and operate nuclear weapons.
What if the top hit is a personal website describing the crime and its effects, rather than a town newspaper--should Google knock that personal website off the front page?