About a minute after I start OneNote 2007, the following warning appears:

*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
OneNote cannot index notes for fast searching because the
Windows Search service is currently stopped or disabled.

You can manually start the Windows Search service in
Administrative Tools in the Windows Control Panel or contact
your system administrator to start the service for you.

[ ] Don't show this again
*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*

I have Windows Desktop Search (WDS) v03.01.6000.72 installed and the
"Windows Search" service is running and is set to start automatically.

A desktop search does find OneNote content, but searching within OneNote
itself does not use WDS; it is the slower 'page by page' search.

The problem started about a month ago (I'm not aware of any changes that
took place). I've rebuilt the WDS index a couple of times and last week I
updated WDS to 3.01 and rebuilt the index yet again, but the problem still
occurs.

Anyone have any ideas?