People just don't seem to know how to do fuzzy searching. Xcode has the same problem. I used Xcode every day for 2 years and its fuzzy matching never once made me happy.

Fortunately, I have a concrete solution: copy what Visual Assist does. Space-separated substrings. It makes it very easy to be more precise about what you're looking for, while still letting you be vague when you'd rather, and the computer never has to make a judgement call.

See here: http://docs.wholetomato.com/default.asp?W193 and search for "filtering in the dialog" (their page has no anchors! - I'm certainly not suggesting you should copy their HTML style)