Would you accept an approximation for results as you type, with the true, exact search happening when you stop typing? I think this would be very useful, especially since I don't need to search the absolute real-time index of my emails 99% of the time. It would probably confuse users, though- having a new result pop in .5 seconds later.