Indexing problem with Vista and Outlook 2007

I have the RTM of both programs, though previously I had beta of Office 2007
on this machine (removed, then RTM installed).

Every time I try to do a search in Outlook, it complains that the index
isn't completed. When I check the indexed items waiting, I find that the
number never changes unless I receive new mail, in which case it goes up with
the new mail. If I do a rebuild, it finishes successfully, and everything
works, until I get additional mail.

Any ideas?

I'm having the same issue and it's been going on for a long time. I have rebuilt the index using the indexing option in control panel and it shows "complete" but when I try to search in Outlook 2007, it tells me that "the search results may be incomplete because items are still being indexed". Arrrgh... Were you able to get it fixed? Thanks.