I actually considered this and settled on prefix matching. I thought most of the time, people would know the exact name of the category they were looking for, and it'd be better to quickly narrow down to it without a lot of extra results.
Do you mind sharing what category you were searching for, and what criteria you typed in? A nice compromise might be prefix matching on each word in a category name; I'm wondering if that would've helped in your case.
Funnily enough the type of example I would have is when I'm writing a post for LiveSide. As you can imagine, we have lots of categories that start with "Windows Live", so having the ability to type say "writer" and have it show me "Windows Live Writer" would be much better than having to type the whole thing.SL - Windows Live Platform MVP