A new version of Windows Desktop Search was released which got installed with the Windows Live Toolbar. Some features introduced/updated are:

1) Outlook Integrated Results- In Outlook 2003, a new folder called Windows Desktop Search is created under the personal folders where in you can search and view results from Outlook data. You can even save search queries which is kinda cool.
2) The WDS Indexer has undergone some major changes to reduce disk I/O while indexing.
3) Shutdown times have been improved significantly (Oh, that annoying End Now pop up!)

Its been over a day since I installed the Outlook add-in for Outlook 2003 but it hasn’t updated the index nor do I find an option to force an update of the index.

Download WDS here

Update::
WDS generated a message today automatically in my Outlook Search folder with the following message:

Where are my results?
The reason you do not see any search results from Windows Desktop Search is because of one of the following:

You do not have Windows Desktop Search installed. Please go to http://desktop.msn.com to install.

or

You are using Outlook Web Access which does not support desktop search
Thank you for using our product!

- The Desktop Search team

So even though I had a process WindowsSearch.exe I was misled. I thought I already had WDS installed when it downloaded the Outlook add-in!!

From Brandonlive.com