OS X has led the way in “search to do that thing you want”, but other than QuickSilver (which is not a part of OS X, but an app that practically every power user has because it’s a faster app launcher than anything that comes in the box*) it doesn’t feature a whole lot in the way of fuzzy matching. A lot of fairly hardcore Mac users are surprised when I tell them this, but the “Help” menu most of them are too proud to look at has a “search” feature for finding menu items... still, no typos allowed

Fuzzy matching is just plain awesome, and adding it to the menu system is an important step forward in usability (then again, I’m a vim addict, so I’m kind of all about the easily-typed keyboard commands).
* QuickSilver is much, much more than just an app launcher, but that’s what most people use it for.