This just seems like it's co-opting the url into a "search". Just have a normal search page where users can type in what they want if they want fuzzy matching. Or have the 404 page contain a search page. I don't think using the url as a "fuzzy search" is the right application.
You can do this and still 404, even. There is rarely a good reason not to 404 when you don’t recognize the URL, even if you want to try to do something helpful with the 404 page.
Yup. I would highly recommend a helpful 404 page rather than "silently" redirecting the user to a different page that they didn't type. Just put a search box, a link to the homepage and "Did you mean these similar pages:" with a list of links.
