OK, the winner is Yahoo Spelling Suggestion
(which uses Yahoo API). This gives your site the possibility to suggest exactly what Yahoo Search suggests
Awesome, I would say!
Here is a short summary about using it, if you guys want to use it too: it requires a Yahoo API key, which can be got free. It is limited to 5000 queries per day, so I suggest caching the suggestion (which I implemented, as my site has more then 5000 searches per day). The page returned by Yahoo needs to be parsed, and see if there is a suggestion given. This
is a page that gives a suggestion, this
is one that has no suggestion.
You can see it live on my shareware site: http://www.coredownload.com/
try some mistypes, like "enail backup", "rgistry cleaner" or whatever you want. I also implemented a function to make bold italic the words that are different between the search query and the suggestion from Yahoo.
If you need assistance on implementing this on your site, let me know.