I'm another engineer at Cue, and I'd like to elaborate on this. We need search, and we'll keep on needing it, because our service is not all-knowing. No matter how cleverly we may predict what you're going to want to see next, we can't possibly predict everything; there always needs to be a way for you to search for things. We know this, and that's why, far from deprecating our search functionality, we're always trying to improve it. The goal is to minimize the time it takes to find whatever you're looking for.
This has been one of our most requested features. It is definitely something that will happen, but I can't comment on timeframe.
When the iCal support ships, I expect you can use that to keep us sync'd even before we have native exchange support. An exchange endpoint is how google sync keeps my phone up to date with ical events, iirc.
