I tend to get several thousand results when I search for just about anything. Most of which aren't related to what I was searing for either :) I think they still need to fine tune the search a bit.
Yes, our next upgrade will feature indexed searches (same technology Links SQL uses) as well as support for MySQL's built in Full Text Indexes. Should see a dramatic improvement in search usefullness as well as speed.