One solution i can imagine for this is to rely on eZ Find, powerful search engine extension for eZ Publish (learn more and try there : http://ez.no/ezfind ). One of its main features, directly mapped to Solr's eponymous feature : More Like This, can help you achieve the smart 404 idea.
Performing a text-based more-like-this query, with the requested URL as base text, could work.
Let us know how it goes, Cheers !
--
Nicolas Pastorino
Director Community - eZ
Member of the Community Project Board