The just-released beta of Windows Search 4.0 is certainly faster than the previous version of Vista search --- but it still suffers from a confusing interface and occasionally incomprehensible behavior. Microsoft needs to realize that it's not just speed that's needed when you search, but intelligence as well.
First the good news -- revamped Search is lightning fast. I haven't been able to devise speed tests, but I can vouch that results appear far more quickly than previously. This is true in Outlook as well, because Vista Search integrates into Outlook. Microsoft claims that search is 33% faster than previously, and that doesn't surprise me at all.