and wondering if it would be easy to do with Newton? (I guess this is really a question for Ed and Lihua).
Newton (or Voyagers web interface, both the old version and the forthcoming version now used by OU) are niggly about returning 'no results', both preferring to stick a message at the top of the screen that basically says 'you suck at searching', rather than giving the user anything useful, or even much space to add a search box.
The newer version will come online for us at some point next year (currently an issue of some debate), so we could experiment with that. It is XML based, so could be re-jigged to include helpful information more easily. As always, we would need to ensure that a human was at the other end of the chat interface. Otherwise, we would just be saying 'your searching sucks and I don't want to talk to you'.
On a similar basis, I would like to pass the search term to Google's spellcheck API, although currently a limit on daily usage prevents this from being workable, otherwise everyone would have done it.
Also of interest is the BL's new pages:
Clever search results there, with a 'top 5' of everything being shown.