This was good enough reason to make me install Windows Search 4.0:
Great improvements have been made with regards to performance. Even now as Preview, Windows Search 4.0 has query response time about 33%faster than search queries in Windows Vista RTM.
Restart of the PC was needed.
I recommend doing the installation the last thing you do and leave the computer running as the index needs to be rebuilt. If you have Outlook make sure to have it up and running as well or the mailboxes will not be indexed. I also suggest that you run SCANPST to fix any potential problems with your PST files.
Many hours later the re-indexing was done. It really is a notable speed increase when searching among the thousands of emails.
For more see the Vista blog post Announcing the Windows Search 4.0 Preview