The latest version of Relevanssi, 2.1, adds a new feature. Well, it's an old one, borrowed from Google, but I haven't seen it in a WordPress plugin yet: "Did you mean" type suggestions when the search fails to produce results!
I got the idea few days ago and whipped up something to that effect. It wasn't very difficult to do, but I do admit the results aren't quite as impressive as with Google. However, the system learns and if you've had the search logging enabled for a long time, the results can be very good.
The feature is pretty experimental so far, so I would love to hear some feedback about it.
I also added a nice little shortcode to make linking to search results easier. That has a side effect of making the suggestions better, too.