The diminutive little search box in FogBugz is one of the most powerful under-utilized features, IMHO. Plenty of people use it for full text search, e.g. widget server database specification, but there are actually many wonderful axes you can use.
It would be a lot easier to use them if they auto-completed liks this:

In this mockup, Instead of FogBugz only showing you the recent searches you've run, it stars with a list of search axes that your text matches. Typing "proj", FogBugz shows you that the project: axis matches.
This could be a lot better than my crappy mockup. A couple of products which do this thing well are Remember the Milk's iPhone client, and YouTrack.