Here's the Bing Instant: http://www.istartedsomething.com/livesearch/

It's actually from a year ago. It doesn't automatically search for a predicted query, just uses what you've typed in so far. But you can mouse over the query suggestions to search for them.

I don’t think that Google or Microsoft care much when ten, one-hunred or one-thousand users suddenly search five times as often as before (as is the case with this project). Problems only start to appear when suddenly every single user searches five times as much. That’s a huge difference (from infinitesimal to 5 times the demands on the infrastructure).

That doesn’t answer your question why Microsoft couldn’t handle it but a small project is also no evidence that Microsoft could do it.