Just came across a link to the new Snap search engine. Not sure if it's doing anything drastically different under the covers, but they are trying some new stuff in the UI (which may be a bit densely packed, actually).
The biggest thing they are trying is a javascript live-updating results display panel. You do your search, then refine it in another field, with the filtered results displaying in almost real time. No visible roundtrip to the server (but there may/must be one in there somewhere...)
Top right in this image is a list of "related keywords" - very cool, and sorta plays into the bag-of-keywords thing again...
Looks promising, if only as a source of *ahem* inspiration...