Outlook Indexing Problems

The search function in Outlook (Office 2010) was working fine for me until yesterday. In trying to fix the problem through reading some advice on various forums, etc., I decided to rebuild the index (which I'm now concluding may have been a bad idea). Anyway, this is going excruciatingly slow and, in fact, I think it may not be going at all. See attached screenshot. It shows 0 items indexed and this was after I let it run overnight.

Or maybe somebody can tell me that this is normal and it just takes a while?

Thanks!

To further complicate the issue, I realized that when I restart the computer, the indexing starts all over. So even though it progressed by about 1,000 when I let it run overnight, it was back to over 39,000 items to be indexed when I rebooted.

I'm hoping somebody can help me with this. An update: I decided to let indexing run for one email account at a time so that it would do it in smaller chunks. I let it run overnight for one email account and this morning it says it finished indexing for that account. However, when I try to search emails in that account, it tells me that there are no matches found. So either it didn't really index that account or for some reason it's not finding anything within the index.

Help!

Thanks!