Outlook 2007 Error

I’ve been using Outlook 2007 for about a year now and havent’ experianced any major problems, until this week. I went to do a search in my Inbox and received “Search results may be incomplete because items are still being indexed”. I tried to rebuild the index with no luck and I have also run the scanpst utility and that didn’t work either. Besides reinstalling Outlook is there anything else I can try?
Thanks,
Kevin