I'm currently working on an app that does search in a limited domain (travel). The current interface is via a dialog textbox, where the user enters sentences or phrases as queries. While natural language offers lots of flexibility I'm realizing this kind of interface is inherently problematic. First, parsing the natural language can be tricky as there are many possibilities. Second, and probably more important, it's a blind interface. We have various types of data and functionality on how to search and present it. It becomes a kind of guessing game whether the user can form a search query that will hit our data and search capabilities. Unless they happen to hit pay dirt it becomes frustrating for the user. At the same time it feels like the user isn't seeing the best of what we can do for them.
I'm sure I'm not the first to run into this. Do you have experience/ideas/research on how to improve/replace such an interface?
Search interface for Zappos.com that includes more granular price information? [more inside]
How can I change the behavior of searching in windows in Firefox? The Firefox search-in-browser bar is, and has always has been, awful. [more inside]
What are some examples of newspaper, magazine, or content archive sites that you think have really good search interfaces? [more inside]