I was setting up a new MOSS dev environment on Windows 2008 June CTP today, and after getting Outlook 2007 installed and configured, I opened it expecting to be taken to the Windows Desktop Search download site. Nope...
Instead, I saw a different message pop up saying 'The Windows Search service is not installed. Outlook cannot provide fast search results when using the new Instant Search feature unless the service is installed.'
Being that Windows 2008 service management is new to me, I had no idea how to set this up, even after poking around a little bit in the role and feature manager.
Found this article on Olav Tollefsen's blog which explains how to enable the Windows Search Service in Windows Server 2008.
Here's what Olav says to do:
1) Start Server Manager
2) Click on Roles in the left navigation pane
3) Select Add Role in the Roles Summary pane to the right
4) Select the File Services role and click Next
5) Select the Windows Search role service