Brandon from the Windows Search team here.
WDS 3.01 (and Vista) do support indexing of Outlook, including Outlook 2003 (and everything else after Outlook 2000). After installing WDS 3.01, the next time you run Outlook it should set itself up for indexing. If you have Outlook running, try restarting it and then looking in the Indexing Options control panel again.
You do NOT have to change the settings for PST files, and in fact you should not. WDS does not index PST files, it indexes Outlook items via the MAPI protocol - so in order for the contents of a PST to be indexed it must be loaded in Outlook and Outlook must be running. There are a number of reasons for this, including authentication which Outlook handles automatically.
As for when indexing occurs - After the initial index is built, WDS will receive notifications every time a change is made to the filesystem or to Outlook. It will then put those notifications in a queue, and process them in the background. If you are using the PC (or there is high CPU usage, hard disk usage, etc), those notifications will be processed more slowly. If your PC is idle, they will be processed immediately. You can also use the WDS tray icon / status window to control the indexer. Pressing "Index Now" will process the notification queue immediately. Pressing "Snooze" will stop processing of notifications completely for the duration of the snooze operation, however notifications will still be queued so that WDS doesn't lose track of changes you've made (files deleted, moved, etc).
On a more modern PC, you can enable the "Index Now" function and just leave it enabled. This is how I run my desktop systems, as it means the indexer always processed notifications immediately - keeping the index always up-to-date. In my experience, this has no negative impact on performance. But that will of course vary by your system and configuration.
As for comments about the Deskbar taking up too much space, that's why it was moved into the Start Menu on Vista =) On Vista, you just click on the Start button and start typing (or press the Windows key then start typing) to perform a search. Though you'd be surprised how often people ask to have the search box back
on the Taskbar... no idea why, though.
Hope that helps address some of the questions/concerns here. You can also visit my blog where I frequently write about WDS and Vista. http://brandonlive.com
Or e-mail me, brandon[AT]brandonlive.com