I usually perform a search using the data I can get from the URL. I usually get a category and some keyword (from the clean title URLs) so I can indicate that there's a 404 and then offer some related results doing a search.

Angel